#### [SOLVED] Get the cartesian product of a series of lists?

By ʞɔıu

How can I get the Cartesian product (every possible combination of values) from a group of lists?

Input:

``````somelists = [
[1, 2, 3],
['a', 'b'],
[4, 5]
]
``````

Desired output:

``````[(1, 'a', 4), (1, 'a', 5), (1, 'b', 4), (1, 'b', 5), (2, 'a', 4), (2, 'a', 5) ...]
``````

#### @Jai 2018-12-31 18:32:17

Recursive Approach:

``````def rec_cart(start, array, partial, results):
if len(partial) == len(array):
results.append(partial)
return

for element in array[start]:
rec_cart(start+1, array, partial+[element], results)

rec_res = []
some_lists = [[1, 2, 3], ['a', 'b'], [4, 5]]
rec_cart(0, some_lists, [], rec_res)
print(rec_res)
``````

Iterative Approach:

``````def itr_cart(array):
results = [[]]
for i in range(len(array)):
temp = []
for res in results:
for element in array[i]:
temp.append(res+[element])
results = temp

return results

some_lists = [[1, 2, 3], ['a', 'b'], [4, 5]]
itr_res = itr_cart(some_lists)
print(itr_res)
``````

#### @Mike Lu 2016-12-10 01:40:56

A minor modification to the above recursive generator solution in variadic flavor:

``````def product_args(*args):
if args:
for a in args[0]:
for prod in product_args(*args[1:]) if args[1:] else ((),):
yield (a,) + prod
``````

And of course a wrapper which makes it work exactly the same as that solution:

``````def product2(ar_list):
"""
>>> list(product(()))
[()]
>>> list(product2(()))
[]
"""
return product_args(*ar_list)
``````

with one trade-off: it checks if recursion should break upon each outer loop, and one gain: no yield upon empty call, e.g.`product(())`, which I suppose would be semantically more correct (see the doctest).

Regarding list comprehension: the mathematical definition applies to an arbitrary number of arguments, while list comprehension could only deal with a known number of them.

#### @Triptych 2009-02-10 19:58:01

In Python 2.6+

``````import itertools
for element in itertools.product(*somelists):
print(element)
``````

Documentation: Python 3 - itertools.product

#### @brian buck 2011-01-13 22:51:51

Just wanted to add the '*' character is required if you use the variable somelists as provided by the OP.

#### @galois 2015-08-12 08:56:08

any idea the efficiency of the `itertools.product()` code? I assume it's been optimized, but just curious (and I don't know how to calculate it from the docs page...)

#### @jfs 2015-08-14 22:08:20

@jaska: `product()` generates `nitems_in_a_list ** nlists` elements in the result (`reduce(mul, map(len, somelists))`). There is no reason to believe that yielding a single element is not `O(nlists)` (amortized) i.e., the time complexity is the same as for simple nested `for`-loops e.g., for the input in the question: `nlists=3`, total number of elements in the result: `3*2*2`, and each element has `nlists` items (`3` in this case).

#### @Vineet Kumar Doshi 2015-08-25 09:04:48

What is the use of `*` before somelists? What does it do?

#### @Moberg 2015-09-15 06:20:12

@VineetKumarDoshi: Here it is used to unpcak a list into multiple arguments to the function call. Read more here: stackoverflow.com/questions/36901/…

#### @igo 2017-09-13 12:35:47

Note: This works only if each list contains at least one item

#### @normanius 2018-12-05 23:18:53

Just a detail, but note that `itertools.product()` can also handle generators, and not just list-like objects.

#### @weiyixie 2017-02-21 04:03:40

Although there are many answers already, I would like to share some of my thoughts:

## Iterative approach

``````def cartesian_iterative(pools):
result = [[]]
for pool in pools:
result = [x+[y] for x in result for y in pool]
return result
``````

## Recursive Approach

``````def cartesian_recursive(pools):
if len(pools) > 2:
pools[0] = product(pools[0], pools[1])
del pools[1]
return cartesian_recursive(pools)
else:
pools[0] = product(pools[0], pools[1])
del pools[1]
return pools
def product(x, y):
return [xx + [yy] if isinstance(xx, list) else [xx] + [yy] for xx in x for yy in y]
``````

## Lambda Approach

``````def cartesian_reduct(pools):
return reduce(lambda x,y: product(x,y) , pools)
``````

#### @Sachin S 2017-07-16 15:44:01

In "Iterative Approach", why is result declared as result = [[]] I know that it is list_of_list but in general even if we have declare list_of_list we use [] and not [[]]

#### @Johnny Boy 2018-12-10 17:03:48

I'm a bit of a newby in terms of Pythonic solutions. Would you or some passerby please write the list comprehension in the "iterative approach" in separate loops?

#### @user3850 2009-02-10 20:02:47

In Python 2.6 and above you can use 'itertools.product`. In older versions of Python you can use the following (almost -- see documentation) equivalent code from the documentation, at least as a starting point:

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

The result of both is an iterator, so if you really need a list for furthert processing, use `list(result)`.

#### @Triptych 2009-02-10 20:05:28

Per the documentation, the actual itertools.product implementation does NOT build intermediate results, which could be expensive. Using this technique could get out of hand quite quickly for moderately sized lists.

#### @user3850 2009-02-10 20:19:45

i can only point the OP to the documentation, not read it for him.

#### @Triptych 2009-03-10 21:07:08

The code from the documentation is meant to demonstrate what the product function does, not as a workaround for earlier versions of Python.

#### @user1035648 2016-11-21 08:42:02

I would use list comprehension :

``````somelists = [
[1, 2, 3],
['a', 'b'],
[4, 5]
]

cart_prod = [(a,b,c) for a in somelists[0] for b in somelists[1] for c in somelists[2]]
``````

#### @llekn 2016-11-30 17:38:05

I really like this solution using list comprehensions. I don't know why isn't upvoted more, it's so simple.

#### @Bằng Rikimaru 2017-01-16 15:33:18

@llekn because the code seems to be fixed to the number of lists

#### @Tyler Heers 2015-10-29 22:28:11

Just to add a bit to what has already been said: if you use sympy, you can use symbols rather than strings which makes them mathematically useful.

``````import itertools
import sympy

x, y = sympy.symbols('x y')

somelist = [[x,y], [1,2,3], [4,5]]
somelist2 = [[1,2], [1,2,3], [4,5]]

for element in itertools.product(*somelist):
print element
``````

#### @Anurag Uniyal 2013-06-14 06:08:27

Here is a recursive generator, which doesn't store any temporary lists

``````def product(ar_list):
if not ar_list:
yield ()
else:
for a in ar_list[0]:
for prod in product(ar_list[1:]):
yield (a,)+prod

print list(product([[1,2],[3,4],[5,6]]))
``````

Output:

``````[(1, 3, 5), (1, 3, 6), (1, 4, 5), (1, 4, 6), (2, 3, 5), (2, 3, 6), (2, 4, 5), (2, 4, 6)]
``````

They're stored in the stack, though.

#### @Anurag Uniyal 2015-03-16 22:42:42

@QuentinPradet do you mean a generator like `def f(): while True: yield 1` will keep on increasing its stack size as we go through it?

no, but def f(): yield 1; f() will, right?

#### @Anurag Uniyal 2015-03-17 16:14:57

@QuentinPradet yeah, but even in this case only the stack needed for max depth, not the whole list, so in this case stack of 3

It's true, sorry. A benchmark could be interesting. :)

#### @SilentGhost 2009-02-10 20:01:26

with itertools.product:

``````import itertools
result = list(itertools.product(*somelists))
``````

#### @Vineet Kumar Doshi 2015-08-25 09:04:29

What is the use of `*` before somelists?

#### @hhh 2016-02-15 23:13:20

@VineetKumarDoshi "product(somelists)" is a cartesian product between the sublists in a way that Python first get "[1, 2, 3]" as an element and then gets other element after next comman and that is linebreak so the first product term is ([1, 2, 3],), similary for the second ([4, 5],) and so "[([1, 2, 3],), ([4, 5],), ([6, 7],)]". If you wanna get a cartesian product between elements inside the tuples, you need to tell Python with Asterisk about the tuple structure. For dictionary, you use **. More here.

#### @jfs 2009-02-10 20:38:16

For Python 2.5 and older:

``````>>> [(a, b, c) for a in [1,2,3] for b in ['a','b'] for c in [4,5]]
[(1, 'a', 4), (1, 'a', 5), (1, 'b', 4), (1, 'b', 5), (2, 'a', 4),
(2, 'a', 5), (2, 'b', 4), (2, 'b', 5), (3, 'a', 4), (3, 'a', 5),
(3, 'b', 4), (3, 'b', 5)]
``````

Here's a recursive version of `product()` (just an illustration):

``````def product(*args):
if not args:
return iter(((),)) # yield tuple()
return (items + (item,)
for items in product(*args[:-1]) for item in args[-1])
``````

Example:

``````>>> list(product([1,2,3], ['a','b'], [4,5]))
[(1, 'a', 4), (1, 'a', 5), (1, 'b', 4), (1, 'b', 5), (2, 'a', 4),
(2, 'a', 5), (2, 'b', 4), (2, 'b', 5), (3, 'a', 4), (3, 'a', 5),
(3, 'b', 4), (3, 'b', 5)]
>>> list(product([1,2,3]))
[(1,), (2,), (3,)]
>>> list(product([]))
[]
>>> list(product())
[()]
``````

#### @jfs 2009-02-10 21:43:51

The recursive version doesn't work if some of `args` are iterators.

#### @Jason Baker 2009-02-10 19:58:31

``````import itertools
>>> for i in itertools.product([1,2,3],['a','b'],[4,5]):
...         print i
...
(1, 'a', 4)
(1, 'a', 5)
(1, 'b', 4)
(1, 'b', 5)
(2, 'a', 4)
(2, 'a', 5)
(2, 'b', 4)
(2, 'b', 5)
(3, 'a', 4)
(3, 'a', 5)
(3, 'b', 4)
(3, 'b', 5)
>>>
``````

### [SOLVED] How do I check if a list is empty?

• 2008-09-10 06:20:11
• Ray Vega
• 2271305 View
• 3236 Score
• Tags:   python list

### [SOLVED] How do I list all files of a directory?

• 2010-07-08 19:31:22
• duhhunjonn
• 3307183 View
• 3475 Score
• Tags:   python directory

### [SOLVED] Getting the last element of a list

• 2009-05-30 19:28:53
• Janusz
• 1660551 View
• 1712 Score
• Tags:   python list indexing

### [SOLVED] How do I get the number of elements in a list?

• 2009-11-11 00:30:54
• y2k
• 3085855 View
• 1786 Score
• Tags:   python list