Get the Cartesian Product of a Series of Lists

Get the cartesian product of a series of lists?

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)

Cartesian product of two lists in python

Do a list comprehension, iterate over both the lists and add the strings, like

list3 = [i+str(j) for i in list1 for j in list2]

How to get a Cartesian product of a list containing lists?

Here is a LINQ extension method using Aggregate:

public static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this IEnumerable<IEnumerable<T>> sequences) =>
    sequences.Aggregate(
        Enumerable.Empty<T>().AsSingleton(),
        (accumulator, sequence) => accumulator.SelectMany(
            accseq => sequence,
            (accseq, item) => accseq.Append(item)));

You need the extension method AsSingleton:

public static IEnumerable<T> AsSingleton<T>(this T item) => new[] { item };

This is based on this answer from @EricLippert.

Getting the cartesian product of two lists as a list-of-lists

well, you just needed one more level of list.

deck = [[x+y for x in value] for y in deck_types]

n-fold Cartesian product on a single list in Python

itertools.product takes a keyword argument to indicate the given arguments should be repeated.

>>> from itertools import product
>>> list(product([1,2], repeat=0))
[()]
>>> list(product([1,2], repeat=1))
[(1,), (2,)]
>>> list(product([1,2], repeat=2))
[(1, 1), (1, 2), (2, 1), (2, 2)]

This works with multiple iterables as well.

# Equivalent to list(product([1,2], ['a', 'b'], [1,2], ['a', 'b']))
>>> list(product([1,2], ['a', 'b'], repeat=2))
[(1, 'a', 1, 'a'), (1, 'a', 1, 'b'), (1, 'a', 2, 'a'), (1, 'a', 2, 'b'), (1, 'b', 1, 'a'), (1, 'b', 1, 'b'), (1, 'b', 2, 'a'), (1, 'b', 2, 'b'), (2, 'a', 1, 'a'), (2, 'a', 1, 'b'), (2, 'a', 2, 'a'), (2, 'a', 2, 'b'), (2, 'b', 1, 'a'), (2, 'b', 1, 'b'), (2, 'b', 2, 'a'), (2, 'b', 2, 'b')]

Improving the performance of cartesian product of multiple lists

A few comments:

• If you think about it, what car_multiple_sets is doing is iterating on its parameter lists. You're doing that using recursion, but iterating on a list can also be done with a for-loop. And it so happens that recursion is somewhat slow and memory-inefficient in python, so for-loops are preferable.

• You don't need to convert to str to group the ints together. You can use tuples. That's precisely what they're for. Replace str(x)+str(y) with (x,y) to get a pair of two integers instead of a string.

def car_two_sets(a, b, unpack=False):
    if unpack:
        return [(*x, y) for x in a for y in b]
    else:
        return [(x, y) for x in a for y in b]

def car_multiple_sets(lists):
    if len(lists) == 0:
        return [()]   # empty Cartesian product has one element, the empty tuple
    elif len(lists) == 1:
        return list(zip(lists[0]))   # list of "1-uples" for homogeneity
    else:
        result = car_two_sets(lists[0], lists[1])
        for l in lists[2:]:
            result = car_two_sets(result, l, unpack=True)
        return result

print( car_multiple_sets((range(3), 'abc', range(2))) )
# [(0, 'a', 0), (0, 'a', 1), (0, 'b', 0), (0, 'b', 1), (0, 'c', 0), (0, 'c', 1),
#  (1, 'a', 0), (1, 'a', 1), (1, 'b', 0), (1, 'b', 1), (1, 'c', 0), (1, 'c', 1),
#  (2, 'a', 0), (2, 'a', 1), (2, 'b', 0), (2, 'b', 1), (2, 'c', 0), (2, 'c', 1)]

---

Related Topics