389
votes

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) ...]
15
be aware that 'every possible combination' is not quite the same as 'Cartesian product', since in Cartesian products, duplicates are allowed.Triptych
Is there a non duplicate version of cartesian product?KJW
@KJW Yes, set(cartesian product)NoBugs
There should be no duplicates in a Cartesian product, unless the input lists contain duplicates themselves. If you want no duplicates in the Cartesian product, use set(inputlist) over all your input lists. Not on the result.CamilB
Mathematically, a Cartesian product is a set, so a Cartesian product does not contain duplicates. On the other hand, itertools.product will have duplicates in the output if the inputs have duplicates. So itertools.product is not strictly speaking the Cartesian product, unless you wrap the inputs in set, as mentioned by @CamilB.Cameron Bieganek

15 Answers

466
votes

itertools.product

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)
96
votes
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)
>>>
42
votes

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

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

with itertools.product:

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

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

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

10
votes

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

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

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.

1
votes

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.

1
votes

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 {()}
0
votes

With early rejection:

def my_product(pools: List[List[Any]], rules: Dict[Any, List[Any]], forbidden: List[Any]) -> Iterator[Tuple[Any]]:
    """
    Compute the cartesian product except it rejects some combinations based on provided rules
    
    :param pools: the values to calculate the Cartesian product on 
    :param rules: a dict specifying which values each value is incompatible with
    :param forbidden: values that are never authorized in the combinations
    :return: the cartesian product
    """
    if not pools:
        return

    included = set()

    # if an element has an entry of 0, it's acceptable, if greater than 0, it's rejected, cannot be negative
    incompatibles = defaultdict(int)
    for value in forbidden:
        incompatibles[value] += 1
    selections = [-1] * len(pools)
    pool_idx = 0

    def current_value():
        return pools[pool_idx][selections[pool_idx]]

    while True:
        # Discard incompatibilities from value from previous iteration on same pool
        if selections[pool_idx] >= 0:
            for value in rules[current_value()]:
                incompatibles[value] -= 1
            included.discard(current_value())

        # Try to get to next value of same pool
        if selections[pool_idx] != len(pools[pool_idx]) - 1:
            selections[pool_idx] += 1
        # Get to previous pool if current is exhausted
        elif pool_idx != 0:
            selections[pool_idx] = - 1
            pool_idx -= 1
            continue
        # Done if first pool is exhausted
        else:
            break

        # Add incompatibilities of newly added value
        for value in rules[current_value()]:
            incompatibles[value] += 1
        included.add(current_value())

        # Skip value if incompatible
        if incompatibles[current_value()] or \
                any(intersection in included for intersection in rules[current_value()]):
            continue

        # Submit combination if we're at last pool
        if pools[pool_idx] == pools[-1]:
            yield tuple(pool[selection] for pool, selection in zip(pools, selections))
        # Else get to next pool
        else:
            pool_idx += 1

I had a case where I had to fetch the first result of a very big Cartesian product. And it would take ages despite I only wanted one item. The problem was that it had to iterate through many unwanted results before finding a correct one because of the order of the results. So if I had 10 lists of 50 elements and the first element of the two first lists were incompatible, it had to iterate through the Cartesian product of the last 8 lists despite that they would all get rejected.

This implementation enables to test a result before it includes one item from each list. So when I check that an element is incompatible with the already included elements from the previous lists, I immediately go to the next element of the current list rather than iterating through all products of the following lists.

-1
votes

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']]
-1
votes

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)