n-fold Cartesian product on a single list in Python

Question

How to compute the n-fold Cartesian product on a list, that is, A × ... × A (n times), in an elegant (concise) way in Pyhton?

This question is not a duplicate of Get the cartesian product of a series of lists?. I do not want the Cartesian product of a series of lists crossed with each other. I want the Cartesian product of a single list crossed n-times with itself, where n is a parameter given to the function.

Examples:

l = ["a", "b", "c"]
> cart_prod(l, 0)
[]
> cart_prod(l, 1)
[('a',), ('b',), ('c',)]
> cart_prod(l, 2)
[('a', 'a'), ('a', 'b'), ('a', 'c'), ('b', 'a'), ('b', 'b'), ('b', 'c'), ('c', 'a'), ('c', 'b'), ('c', 'c')]
> cart_prod(l, 3)
[('a', 'a', 'a'), ('a', 'a', 'b'), ('a', 'a', 'c'), ('a', 'b', 'a'), ('a', 'b', 'b'), ('a', 'b', 'c'), ('a', 'c', 'a'), ('a', 'c', 'b'), ('a', 'c', 'c'), ('b', 'a', 'a'), ('b', 'a', 'b'), ('b', 'a', 'c'), ('b', 'b', 'a'), ('b', 'b', 'b'), ('b', 'b', 'c'), ('b', 'c', 'a'), ('b', 'c', 'b'), ('b', 'c', 'c'), ('c', 'a', 'a'), ('c', 'a', 'b'), ('c', 'a', 'c'), ('c', 'b', 'a'), ('c', 'b', 'b'), ('c', 'b', 'c'), ('c', 'c', 'a'), ('c', 'c', 'b'), ('c', 'c', 'c')]

I came up with the following iterative solution:

def cart_prod(l, n):
    if n == 0:
        return []  # compute the result for n = 0
    # preliminarily, create a list of lists instead of a list of tuples
    res = [[x] for x in l]  # initialize list with singleton tuples (n = 1)
    for i in range(n-1):
        res = [r + [x] for r in res for x in l]  # concatenate each n-1 tuple with each element from a
    res = [tuple(el) for el in res]  # turn the list of lists into a list of tuples
    return res

This code does the job, but is there a shorter, possibly one-liner definition, maybe a nested list comprehension or a lambda expression? I am interested in more compact solutions, not necessarily more readable ones.

It still looks like a duplicate to me. Just replicate the list and then use `itertools.product`. — bnaecker, Jun 16 '20 at 21:46
Better yet, `itertools.tee` the list `n` times, then use `itertools.product`. — bnaecker, Jun 16 '20 at 21:47

chepner · Accepted Answer · 2020-06-16T21:49:34.223

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

n-fold Cartesian product on a single list in Python

1 Answers1