Recursive generic function for Cartesian product in Python

user_17694979 0
Viewed 212

I'm looking for a way to implement a recursive function to get a generic cartesian product of the same list n times without using the itertools package. The function should get as parameters the list and the n times.

Output Example:

>>> l = [0, 2]
>>> print([(x,y) for x in l for y in l])

>>> [(0, 0), (0, 2), (2, 0), (2, 2)]

But also:

>>> l = [0,2]
>>> print([(x,y,z) for x in l for y in l for z in l])
>>> [(0, 0, 0),(0, 0, 2),(0, 2, 0),(0, 2, 2),(2, 0, 0),(2, 0, 2),(2, 2, 0),(2, 2, 2)]

Or

>>> l = [4,5,8]
>>> print([(x,y) for x in l for y in l])
>>> [(4, 4), (4, 5), (4, 8), (5, 4), (5, 5), (5, 8), (8, 4), (8, 5), (8, 8)]

Etc..

I wanna generalize this for every generic list and every n-tuple. I found different ways to implement this iteratively but none with recursion. Hope anyone can help me.

combinatorics cartesian-product recursion python
2 Answers

Try this

def cartesian_product(lst, n):
    if n == 1:
        return [(x,) for x in lst]
    return [(x,) + t for t in cartesian_product(lst, n - 1) for x in lst]
user_52961060

intuitive

Better than using a fixed integer, I think product(t) should take a list of iterables -

  1. if the input t is empty, yield the empty product, ()
  2. (inductive) t has at least one iterable. for all p in the result of the sub-problem product(t[1:]), for all v in the first iterable t[0], prepend v to p and yield
def product(t):
  if not t:
    yield ()                   # 1. no iterables
  else:
    for p in product(t[1:]):   # 2. at least one iterable
      for v in t[0]:
        yield (v, *p)

My multiplying the input by *2 you can still control the output of product -

for p in product([[1,2]] * 2):
  print(p)

(1, 1)
(2, 1)
(1, 2)
(2, 2)

Now let's multiply by *3 -

for p in product([[1,2]] * 3):
  print(p)

(1, 1, 1)
(2, 1, 1)
(1, 2, 1)
(2, 2, 1)
(1, 1, 2)
(2, 1, 2)
(1, 2, 2)
(2, 2, 2)

flexible

Since any iterable can be used, you can mix/match to your liking -

for p in product([range(2), [3,4], "hi", (9,)]):
  print(p)

(0, 3, 'h', 9)
(1, 3, 'h', 9)
(0, 4, 'h', 9)
(1, 4, 'h', 9)
(0, 3, 'i', 9)
(1, 3, 'i', 9)
(0, 4, 'i', 9)
(1, 4, 'i', 9)

efficient

Use of a generator makes product efficient for use in problems involving combinatorics. Generators allow us to pause/cancel and provide early exit once a desired result is found -

def solveTriangle(min, max):
  for (x,y,z) in product([list(range(min, max))] * 3):
    if x ** 2 + y ** 2 == z ** 2:
      return (x,y,z)               # <- return stops generator
  return None

print(solveTriangle(10,30))

(16, 12, 20)

itertools

Note the itertools module provides product as a built-in function. It's fun to implement product as an exercise, but if you plan to use this in production code, the built-in function probably offers the best performance.

user_6331830
Related