CODEWITHSUNDEEP
pythonlistnumpyindexing
connor449
connor449

Reputation: 1679

How to find which items in list of lists is equal to another list

I have a list of lists that looks like this:

[[0],
[0, 1, 2],
[2],
[3],
[4],
[5],
[0, 1, 2, 3, 4, 5, 6, 7],
[7],
[8],
[9],
[8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18],
[11],
[11, 12, 13, 14, 15, 16, 17, 18],
[13],
[14],
[14, 15, 16, 17, 18],
[16, 17, 18],
[17],
[17, 18]]

I am trying to find the least number of items in the list, when concatenated, that equal the full range of the list. In this case, the full range of the list is this:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]

So in this case, these two items from the list of lists would equal the full range:

[0]
[0, 1, 2]
[2]
[3]
[4]
[5]
---> [0, 1, 2, 3, 4, 5, 6, 7]
[7]
[8]
[9]
---> [8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]
[11]
[11, 12, 13, 14, 15, 16, 17, 18]
[13]
[14]
[14, 15, 16, 17, 18]
[16, 17, 18]
[17]
[17, 18]

Upvotes: 1

Views: 62

Answers (1)

Chris
Chris

Reputation: 29742

One way using itertools.permutations and chain:

from itertools import permutations, chain

starget = sorted(target)
for i in range(2, len(target)):
    for perm in permutations(l, i):
        if sorted(chain(*perm)) == starget:
            print(i, perm)
            break
    break

Output:

2 ([0, 1, 2, 3, 4, 5, 6, 7], [8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18])

Upvotes: 1

Related Questions