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!
you need itertools.product:
>>> import itertools
>>> a = [[1,2,3],[4,5,6],[7,8,9,10]]
>>> list(itertools.product(*a))
[(1, 4, 7), (1, 4, 8), (1, 4, 9), (1, 4, 10), (1, 5, 7), (1, 5, 8), (1, 5, 9), (1, 5, 10), (1, 6, 7), (1, 6, 8), (1, 6, 9), (1, 6, 10), (2, 4, 7), (2, 4, 8), (2, 4, 9), (2, 4, 10), (2, 5, 7), (2, 5, 8), (2, 5, 9), (2, 5, 10), (2, 6, 7), (2, 6, 8), (2, 6, 9), (2, 6, 10), (3, 4, 7), (3, 4, 8), (3, 4, 9), (3, 4, 10), (3, 5, 7), (3, 5, 8), (3, 5, 9), (3, 5, 10), (3, 6, 7), (3, 6, 8), (3, 6, 9), (3, 6, 10)]
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']
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]]
This mostly mimics solutions like Answer by Jarret Hardie using itertools.product, but has these distinctions:
itertools.product in-line, instead of via variable a - so no *args syntax needed on the inline parameters*args syntax with inline product parameters (like product(*[[1,2,3],[4,5,6],[7,8,9,10]])), mypy might still fail it (with something like error: No overload variant of "product" matches argument type "List[object]")mypy, is to not use *args syntax, like this: >>> import itertools
>>> list(itertools.product([1,2,3],[4,5,6],[7,8,9,10]))
[(1, 4, 7), (1, 4, 8), (1, 4, 9), (1, 4, 10), (1, 5, 7), (1, 5, 8), (1, 5, 9), (1, 5, 10), (1, 6, 7), (1, 6, 8), (1, 6, 9), (1, 6, 10), (2, 4, 7), (2, 4, 8), (2, 4, 9), (2, 4, 10), (2, 5, 7), (2, 5, 8), (2, 5, 9), (2, 5, 10), (2, 6, 7), (2, 6, 8), (2, 6, 9), (2, 6, 10), (3, 4, 7), (3, 4, 8), (3, 4, 9), (3, 4, 10), (3, 5, 7), (3, 5, 8), (3, 5, 9), (3, 5, 10), (3, 6, 7), (3, 6, 8), (3, 6, 9), (3, 6, 10)]
This answer isn't as clean as using itertools but the ideas could be useful.
Drawing inspiration from the construction of zip() here, we could do the following.
>>> a = iter([[1,2,3],[4,5,6],[7,8,9,10]])
>>> sentinel = object()
>>> result = [[]]
>>> while True:
>>> l = next(a,sentinel)
>>> if l == sentinel:
>>> break
>>> result = [ r + [digit] for r in result for digit in l]
>>> print(result)
[[1, 4, 7], [1, 4, 8], [1, 4, 9], [1, 4, 10], [1, 5, 7], [1, 5, 8], [1, 5, 9], [1, 5, 10], [1, 6, 7], [1, 6, 8], [1, 6, 9], [1, 6, 10], [2, 4, 7], [2, 4, 8], [2, 4, 9], [2, 4, 10], [2, 5, 7], [2, 5, 8], [2, 5, 9], [2, 5, 10], [2, 6, 7], [2, 6, 8], [2, 6, 9], [2, 6, 10], [3, 4, 7], [3, 4, 8], [3, 4, 9], [3, 4, 10], [3, 5, 7], [3, 5, 8], [3, 5, 9], [3, 5, 10], [3, 6, 7], [3, 6, 8], [3, 6, 9], [3, 6, 10]]
We use a as an iterator in order to successively get the next item of it without needing to know how many there are a priori. The next command will output sentinel (which is an object created solely to make this comparison, see here for some explanation) when we run out of lists in a, causing the if statement to trigger so we break out of the loop.
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')]
