Total combinations from a variable set of lists using itertools

Question

I am using python and I believe the problem below can be solved using itertools but if there is another method please let me know.

If I have a variable set of lists (for illustration purposes let it be 3) and each contains a variable set of elements (elements could be strings, integers, lists).

An example:

                          [a,b,c]   [d,e,f]   [g,h,i]

How can I create (and access) all the total possible combinations (as a list preferably) choosing just one from each set?

i.e.

[a,d,g]

[a,d,h]

[a,d,i]

[a,e,g]

... (and so on)

Order does not matter so for the output I do not want [a,d,g] and [d,a,g] both to show, just [a,d,g].

If my question is not clear please let me know.

Also, if it helps we can consider all elements to be simple strings or integers but I would like a solution that takes in count the fact that the number of lists and the number of elements in each list is variable.

score 0 · Answer 1 · answered Apr 11 '18 at 01:25

0

I don't have the sway to mark as duplicate, but I think you want itertools.product as explained here: pick combinations from multiple lists

answered Apr 11 '18 at 01:25

Debbie Milburn

36
3

score 0 · Accepted Answer · answered Apr 11 '18 at 01:28

You can solve it using a depth first search:

def find_all_combinations(lists):
    res = set() #set so no duplicates
    def dfs(curr_index, curr_combination):
        if curr_index == len(lists): #base case - add to results and stop
            res.add(tuple(sorted(curr_combination)))
        else:
            for i in lists[curr_index]: #iterate through each val in cur index
                dfs(curr_index + 1, curr_combination + [i]) #add and repeat for next index
    dfs(0, [])
    return sorted(list(res))

print(find_all_combinations(l))
>>>[('a', 'd', 'g'), ('a', 'd', 'h'), ('a', 'd', 'i'), ('a', 'e', 'g'), ('a', 'e', 'h'), ('a', 'e', 'i'), ('a', 'f', 'g'), ('a', 'f', 'h'), ('a', 'f', 'i'), ('b', 'd', 'g'), ('b', 'd', 'h'), ('b', 'd', 'i'), ('b', 'e', 'g'), ('b', 'e', 'h'), ('b', 'e', 'i'), ('b', 'f', 'g'), ('b', 'f', 'h'), ('b', 'f', 'i'), ('c', 'd', 'g'), ('c', 'd', 'h'), ('c', 'd', 'i'), ('c', 'e', 'g'), ('c', 'e', 'h'), ('c', 'e', 'i'), ('c', 'f', 'g'), ('c', 'f', 'h'), ('c', 'f', 'i')]

A plus of this is that all of your lists don't have to be the same length.

Total combinations from a variable set of lists using itertools

2 Answers2