python - Python 中笛卡尔积的递归通用函数

Question

我正在寻找一种方法来实现递归函数，以在不使用 itertools 包的情况下获得同一列表 n 次的通用笛卡尔积。 该函数应获取列表和 n 次作为参数。

输出示例:

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

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

而且:

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

或者

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

等等..

我想将其推广到每个通用列表和每个 n 元组。 我找到了不同的方法来迭代实现这个，但没有一个是递归的。希望有人能帮助我。

Answer 1

直观

比使用固定整数更好，我认为 product(t) 应该采用可迭代列表 -

1. 如果输入 t 为空，则生成空乘积，()
2. (归纳)t 至少有一个可迭代对象。对于子问题 product(t[1:]) 的结果中的所有 p，对于第一个可迭代 中的所有 v >t[0]，在 p 前面加上 v 并产生

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)

我将输入乘以*2，您仍然可以控制product的输出 -

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

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

现在让我们乘以*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)

灵活

由于可以使用任何迭代，因此您可以根据自己的喜好进行混合/匹配 -

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)

高效

使用生成器可以使product在涉及组合学的问题中高效使用。一旦找到所需的结果，生成器允许我们暂停/取消并提供提前退出 -

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

注意 itertools 模块提供 product作为内置函数。将 product 作为练习来实现是很有趣的，但如果您计划在生产代码中使用它，内置函数可能会提供最佳性能。