## The Question :

*355 people think this question is useful*

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

*The Question Comments :*

## The Answer 1

*427 people think this answer is useful*

Available from Python 2.6.

import itertools
somelists = [
[1, 2, 3],
['a', 'b'],
[4, 5]
]
for element in itertools.product(*somelists):
print(element)

Which is the same as,

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

## The Answer 2

*88 people think this answer is useful*

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

## The Answer 3

*41 people think this answer is useful*

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

## The Answer 4

*25 people think this answer is useful*

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

## The Answer 5

*22 people think this answer is useful*

with itertools.product:

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

## The Answer 6

*14 people think this answer is useful*

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

## The Answer 7

*11 people think this answer is useful*

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

.

## The Answer 8

*10 people think this answer is useful*

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)

## The Answer 9

*7 people think this answer is useful*

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

## The Answer 10

*3 people think this answer is useful*

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.

## The Answer 11

*1 people think this answer is useful*

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

About sympy.

## The Answer 12

*1 people think this answer is useful*

I believe this works:

def cartesian_product(L):
if L:
return {(a,) + b for a in L[0]
for b in cartesian_product(L[1:])}
else:
return {()}

## The Answer 13

*-1 people think this answer is useful*

**Stonehenge approach:**

def giveAllLists(a, t):
if (t + 1 == len(a)):
x = []
for i in a[t]:
p = [i]
x.append(p)
return x
x = []
out = giveAllLists(a, t + 1)
for i in a[t]:
for j in range(len(out)):
p = [i]
for oz in out[j]:
p.append(oz)
x.append(p)
return x
xx= [[1,2,3],[22,34,'se'],['k']]
print(giveAllLists(xx, 0))

output:

[[1, 22, 'k'], [1, 34, 'k'], [1, 'se', 'k'], [2, 22, 'k'], [2, 34, 'k'], [2, 'se', 'k'], [3, 22, 'k'], [3, 34, 'k'], [3, 'se', 'k']]

## The Answer 14

*-1 people think this answer is useful*

You can use `itertools.product`

in the standard library to get the cartesian product. Other cool, related utilities in `itertools`

include `permutations`

, `combinations`

, and `combinations_with_replacement`

. Here is a link to a python codepen for the snippet below:

from itertools import product
somelists = [
[1, 2, 3],
['a', 'b'],
[4, 5]
]
result = list(product(*somelists))
print(result)