There are multiple sets of elements like:

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

I need an algorithm to get all possible combinations of each element from each set. E.g.

['a', 'e', 'g']
['a', 'f', 'g']
['a', 'f', 'h']
['a', 'f', 'i']
['b', 'e', 'g']

...etc

CodePudding user response：

You can use backtracking to solve this:

def get_perms(arr): 
    def backtrack(idx, partial_res, res): 
        if idx == len(arr): 
            res.append(partial_res[:]) 
            return  
        for i in range(0, len(arr[idx])): 
            partial_res.append(arr[idx][i]) 
            backtrack(idx 1, partial_res, res) 
            partial_res.pop() 
    res = [] 
    backtrack(0, [], res) 
    return res

A quick test:

arr = [['a', 'b', 'c'], ['e', 'f'], ['g', 'h', 'i']]

get_perms(arr)
[['a', 'e', 'g'],
 ['a', 'e', 'h'],
 ['a', 'e', 'i'],
 ['a', 'f', 'g'],
 ['a', 'f', 'h'],
 ['a', 'f', 'i'],
 ['b', 'e', 'g'],
 ['b', 'e', 'h'],
 ['b', 'e', 'i'],
 ['b', 'f', 'g'],
 ['b', 'f', 'h'],
 ['b', 'f', 'i'],
 ['c', 'e', 'g'],
 ['c', 'e', 'h'],
 ['c', 'e', 'i'],
 ['c', 'f', 'g'],
 ['c', 'f', 'h'],
 ['c', 'f', 'i']]

The algorithm just goes over each inner list and adds each element to partial_res and calls itself recursively while incrementing the index to go to the next inner list.

CodePudding user response：

What you want is a Cartesion product. Use itertools:

from itertools import product

matrix = [['a', 'b', 'c'], ['e', 'f'], ['g', 'h', 'i']]
for res in product(*matrix):
    print(list(res))