[python] All combinations of a list of lists

I'm basically looking for a python version of Combination of List<List<int>>

Given a list of lists, I need a new list that gives all the possible combinations of items between the lists.

[[1,2,3],[4,5,6],[7,8,9,10]] -> [[1,4,7],[1,4,8],...,[3,6,10]]

The number of lists is unknown, so I need something that works for all cases. Bonus points for elegance!

Numpy can do it:

 >>> import numpy
 >>> a = [[1,2,3],[4,5,6],[7,8,9,10]]
 >>> [list(x) for x in numpy.array(numpy.meshgrid(*a)).T.reshape(-1,len(a))]
[[ 1, 4, 7], [1, 5, 7], [1, 6, 7], ....]

One can use base python for this. The code needs a function to flatten lists of lists:

def flatten(B):    # function needed for code below;
    A = []
    for i in B:
        if type(i) == list: A.extend(i)
        else: A.append(i)
    return A

Then one can run:

L = [[1,2,3],[4,5,6],[7,8,9,10]]

outlist =[]; templist =[[]]
for sublist in L:
    outlist = templist; templist = [[]]
    for sitem in sublist:
        for oitem in outlist:
            newitem = [oitem]
            if newitem == [[]]: newitem = [sitem]
            else: newitem = [newitem[0], sitem]
            templist.append(flatten(newitem))

outlist = list(filter(lambda x: len(x)==len(L), templist))  # remove some partial lists that also creep in;
print(outlist)

Output:

[[1, 4, 7], [2, 4, 7], [3, 4, 7], 
[1, 5, 7], [2, 5, 7], [3, 5, 7], 
[1, 6, 7], [2, 6, 7], [3, 6, 7], 
[1, 4, 8], [2, 4, 8], [3, 4, 8], 
[1, 5, 8], [2, 5, 8], [3, 5, 8], 
[1, 6, 8], [2, 6, 8], [3, 6, 8], 
[1, 4, 9], [2, 4, 9], [3, 4, 9], 
[1, 5, 9], [2, 5, 9], [3, 5, 9], 
[1, 6, 9], [2, 6, 9], [3, 6, 9], 
[1, 4, 10], [2, 4, 10], [3, 4, 10], 
[1, 5, 10], [2, 5, 10], [3, 5, 10], 
[1, 6, 10], [2, 6, 10], [3, 6, 10]]

from itertools import product 
list_vals = [['Brand Acronym:CBIQ', 'Brand Acronym :KMEFIC'],['Brand Country:DXB','Brand Country:BH']]
list(product(*list_vals))

Output:

[('Brand Acronym:CBIQ', 'Brand Country :DXB'),
('Brand Acronym:CBIQ', 'Brand Country:BH'),
('Brand Acronym :KMEFIC', 'Brand Country :DXB'),
('Brand Acronym :KMEFIC', 'Brand Country:BH')]

The most elegant solution is to use itertools.product in python 2.6.

If you aren't using Python 2.6, the docs for itertools.product actually show an equivalent function to do the product the "manual" way:

def product(*args, **kwds):
    # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
    # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
    pools = map(tuple, args) * kwds.get('repeat', 1)
    result = [[]]
    for pool in pools:
        result = [x+[y] for x in result for y in pool]
    for prod in result:
        yield tuple(prod)

Nothing wrong with straight up recursion for this task, and if you need a version that works with strings, this might fit your needs:

combinations = []

def combine(terms, accum):
    last = (len(terms) == 1)
    n = len(terms[0])
    for i in range(n):
        item = accum + terms[0][i]
        if last:
            combinations.append(item)
        else:
            combine(terms[1:], item)


>>> a = [['ab','cd','ef'],['12','34','56']]
>>> combine(a, '')
>>> print(combinations)
['ab12', 'ab34', 'ab56', 'cd12', 'cd34', 'cd56', 'ef12', 'ef34', 'ef56']

listOLists = [[1,2,3],[4,5,6],[7,8,9,10]]
for list in itertools.product(*listOLists):
  print list;

I hope you find that as elegant as I did when I first encountered it.