All combinations of a list of lists

Question

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!

score 620 · Accepted Answer · edited Sep 29 '14 at 15:22

620

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)]

edited Sep 29 '14 at 15:22

trss

915
1
19
35

answered Apr 28 '09 at 16:54

SilentGhost

307,395
66
306
293

36

Could someone explain the meaning of the asterisk in `*a`? – Serrano Feb 04 '13 at 20:20
68

`*a` means these are arguments being passed to the function or method. `def fn(a,b,c):` would respond to `fn(*[1,2,3])` [reference](http://www.saltycrane.com/blog/2008/01/how-to-use-args-and-kwargs-in-python/) – mjallday Feb 12 '13 at 23:37
1

@mjallday, would it be possible to add also these combinations: (7,4,1),(8,4,1),(9,4,1),(10,4,1),(7,5,1),(8,5,1),(9,5,1),(10,5,1) etc? – Reman Feb 17 '16 at 15:19
2

@Reman It's not entirely clear what you want to get but if it is, for example, also the reverse of each tuple you can use a a wrapper function that takes `a` as input, iterates over `itertools.product(*a)` and `yield`s both the tuple produced by `itertools` and a reverse version (e.g. create a list, `reverse()` it and convert back to tuple). Best ask a new question. – Joachim Wagner Feb 26 '20 at 11:06
if you are familiar with javascript `[*a]` would be the same the js spread operator `[...a]`. This is also true for dicts – Kurtis Streutker Dec 26 '20 at 20:29

score 28 · Answer 2 · edited Feb 15 '22 at 21:20

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)

score 27 · Answer 3 · edited Jun 25 '22 at 03:00

27

Simply use itertools.product:

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

edited Jun 25 '22 at 03:00

Karl Knechtel

62,466
11
102
153

answered Apr 28 '09 at 16:58

Matthew Flaschen

278,309
50
514
539

duanev · Answer 4 · 2022-04-22T16:11:16.880

Nothing wrong with straight up recursion for this task, no need for external dependencies, 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']

score 6 · Answer 5 · edited Jan 31 '17 at 02:48

6

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], ....]

edited Jan 31 '17 at 02:48

Community

1
1

answered Jan 07 '17 at 23:36

Diamantatos Paraskevas

3,874
1
20
15

1

Could someone explain this? – ashishv Dec 07 '17 at 13:53
This does not work if the things in a are arrays. `a=[[[array A], [array B], [array C]], [...]` – nycynik Sep 12 '20 at 02:08
2

this feels like asking 'how do i boil water' and instead of saying 'use a kettle', you get 'lower the atmospheric pressure around the water'. Both work! – Attack68 Feb 12 '21 at 15:20

rnso · Answer 6 · 2019-06-06T00:29:33.600

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]]

cellepo · Answer 7 · 2021-06-10T01:38:21.407

This mostly mimics solutions like Answer by Jarret Hardie using itertools.product, but has these distinctions:

this passes parameters to itertools.product in-line, instead of via variable a - so no *args syntax needed on the inline parameters
if your mypy type-linter acts like mine, and you can get your code to otherwise "work" with the *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]")
So solution to that 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)]

Kweku A · Answer 8 · 2021-07-02T11:04:35.283

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.

Indeed this is more or less what `itertools.product` does, -- see [here](https://docs.python.org/3/library/itertools.html#itertools.product) -- except the use of a sentinel while `itertools.product` uses `yield`. — Kweku A, Jul 02 '21 at 13:20

score -1 · Answer 9 · edited Jul 17 '19 at 08:26

-1

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')]

edited Jul 17 '19 at 08:26

MartenCatcher

2,713
8
26
39

answered Jul 17 '19 at 07:08

Kez

9
1

This answer should be accepted, since it's the only one using a built-in function, while highlighting that it also works for any and also heterogenous types. – pedjjj Oct 24 '19 at 12:42
4

How is this answer any different than the one provided many years ago? – Dawid Laszuk Dec 02 '19 at 01:07
The types of the parameters here are homogenous, not hetrogenous. – cellepo Jun 10 '21 at 01:36

All combinations of a list of lists

9 Answers9

Linked