Categories
cartesian-product list python

Get the cartesian product of a series of lists?

456

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

10

  • 35

    be aware that ‘every possible combination’ is not quite the same as ‘Cartesian product’, since in Cartesian products, duplicates are allowed.

    Feb 10, 2009 at 20:08

  • 9

    Is there a non duplicate version of cartesian product?

    – KJW

    Nov 13, 2013 at 5:32

  • 19

    @KJW Yes, set(cartesian product)

    – NoBugs

    Feb 12, 2015 at 7:04

  • 12

    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

    Aug 24, 2017 at 8:39

  • 8

    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.

    Dec 8, 2020 at 22:56

551

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)

9

  • 30

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

    Jan 13, 2011 at 22:51

  • 5

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

    Aug 25, 2015 at 9:04

  • 11

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

    – Moberg

    Sep 15, 2015 at 6:20

  • 5

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

    – igo

    Sep 13, 2017 at 12:35

  • 8

    @igo it also works when any list contains zero items–the cartesian product of at least one zero sized list and any other lists is an empty list, and that’s exactly what this produces.

    – Ruzihm

    Oct 9, 2019 at 20:42

115

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

1

  • Upvotes for this answer are warranted and encouraged, it’s the easiest answer to read and understand quickly.

    Jan 30, 2021 at 22:13


44

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

1

  • 1

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

    – jfs

    Feb 10, 2009 at 21:43