By ʞɔıu


2009-02-10 19:54:17 8 Comments

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

11 comments

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

@user3850 2009-03-10 22:37:25

your point being?

@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

About sympy.

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

@Quentin Pradet 2015-03-16 11:09:00

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?

@Quentin Pradet 2015-03-17 10:09:56

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

@Quentin Pradet 2015-03-17 18:24:26

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

Related Questions

Sponsored Content

30 Answered Questions

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

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

20 Answered Questions

22 Answered Questions

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

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

11 Answered Questions

[SOLVED] Getting the last element of a list

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

7 Answered Questions

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

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

39 Answered Questions

[SOLVED] How to make a flat list out of list of lists

25 Answered Questions

[SOLVED] How do I concatenate two lists in Python?

34 Answered Questions

[SOLVED] How do I sort a dictionary by value?

15 Answered Questions

[SOLVED] How to clone or copy a list?

28 Answered Questions

[SOLVED] Finding the index of an item given a list containing it in Python

  • 2008-10-07 01:39:38
  • Eugene M
  • 3289677 View
  • 2708 Score
  • 28 Answer
  • Tags:   python list indexing

Sponsored Content