141

How can I get the list of cross product pairs from a list of arbitrarily long lists in Python?

Example

a = [1, 2, 3]
b = [4, 5, 6]

crossproduct(a,b) should yield [[1, 4], [1, 5], [1, 6], ...].

Martin Thoma
  • 124,992
  • 159
  • 614
  • 958

3 Answers3

193

You're looking for itertools.product if you're on (at least) Python 2.6.

>>> import itertools
>>> a=[1,2,3]
>>> b=[4,5,6]
>>> itertools.product(a,b)
<itertools.product object at 0x10049b870>
>>> list(itertools.product(a,b))
[(1, 4), (1, 5), (1, 6), (2, 4), (2, 5), (2, 6), (3, 4), (3, 5), (3, 6)]
ChristopheD
  • 112,638
  • 29
  • 165
  • 179
  • 3
    Note that for pre-2.6 use, you can simply copy-and-paste the pure Python implementation from the linked documentation. – Mike Graham Mar 29 '10 at 21:34
  • 16
    `product()` is not restricted to two parameters thus usable for an arbitrary number of lists (listed themselves) as well. So you can do `list(itertools.product(*[[1,2],[3,4],[5,6]]))` to get `[(1, 3, 5), (1, 3, 6),..` – valid May 20 '13 at 20:59
102

Since you asked for a list:

[(x, y) for x in a for y in b]

But you can avoid the overhead of a list if you're just looping through these by using generators instead:

((x, y) for x in a for y in b)

Behaves identically in a for loop but doesn't result in the creation of a list.

Cory Petosky
  • 12,458
  • 3
  • 39
  • 44
  • 1
    I prefer this method, but can't say why. Maybe because the double looping is explicit? – Rich Sep 02 '11 at 19:14
  • 9
    Nicely pythonic. Or as I like to say, a good example of pythontificocity. – charleslparker Sep 26 '13 at 16:21
  • Thanks! I'm a big fan of code that looks like what it does. – Cory Petosky Sep 27 '13 at 21:32
  • Sorry for the late bump. This looks nice. However, if the OP is looking for Cartesian product, won't this create duplicates and reversed pairs? – dineshdileep Jan 06 '16 at 04:54
  • 1
    I'm not sure exactly what you mean. If `a` and `b` are not sets, and have duplicate elements within themselves, then yes, this can produce duplicate entries. `[(x, y) for x in [1, 1] for y in [2]]` would produce `[(1, 2), (1, 2)]`. But that's the result of applying an mathematical operation defined on sets on non-set input. Reversed pairs will not occur -- anything in the `a` iterable will never appear as the second element of a returned pair unless that element is also in the `b` iterable. – Cory Petosky Jan 07 '16 at 19:36
  • 2
    Explicit is always better than implicit. – ozgur May 07 '16 at 18:32
  • plus 1 for generators. I'm just starting to realize their power. thanks. – Marc Oct 11 '16 at 21:20
  • Pythonic but 200 times slower than `itertools.product`. – Suuuehgi Aug 23 '21 at 13:40
23

Using generators there is no need for itertools, simply:

gen = ((x, y) for x in a for y in b)

for u, v in gen:
    print u, v
Rabih Kodeih
  • 9,361
  • 11
  • 47
  • 55