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，对于第一个可迭代的t[0]中的全部v，将v前置到p，并得出

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作为练习来实现是很有趣的，但如果您计划在生产代码中使用它，那么内置函数可能会提供最佳性能。

Answer 2

试试这个

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