使用递归计算集合的笛卡尔积

Question

我写了一个递归的程序，用来计算两个集合的叉积。

def combine(input1,input2,output):
    if len(input2)==0:
        return output
    else:
       for num in input1:
           output.append((num,input2[0]))
       combine(input1,input2[1:],output)

input1=[1 2 5]
input2=[2 3]
output=[(1,2), (1,3), (2,2),(2,3),(5,2),(5,3)]

我想知道有没有办法让这个递归更好，比如能不能去掉else里的循环，直接在同一个函数里处理。我正在考虑不同的解决方法。

补充说明：我不想用现成的解决方案，比如itertools.product。我想了解如何用不同的方式来做递归，而不是使用它。

Answer 1

使用itertools库

import itertools

print list(itertools.product(input1, input2))

从语义上讲，这个和下面的内容是一样的：

for i_1 in input_1:
    for i_2 in input_2:
        for i_3 in input_3:
            ...
                for i_n in input_n:
                    #do something with i_1, i_2, i_3, ..., i_n

这里的n是你传递给product的参数数量。

Answer 2

我想到的最简单的笛卡尔积的递归定义是这样的。你可以看到，这里有一个循环——实际上是两个循环，嵌套在一个列表推导式中。跟你的不同的是，这个可以处理两个或更多的序列：

def product(*seqs):
    if not seqs:
        return [[]]
    else:
        return [[x] + p for x in seqs[0] for p in product(*seqs[1:])]

接下来，我来给你讲讲它是怎么工作的。根据定义，空序列的笛卡尔积（product()）是一个包含空序列的序列。换句话说，product() 等于 [[]]——想了解更多原因可以看看这里。

现在假设我们调用 product([1, 2, 3])——这时 seqs 不是空的，所以返回值就是列表推导式的结果。在这种情况下，product(*seqs[1:]) 等于 product(*[])，也就是 product()，结果是 [[]]，所以这个列表推导式可以等同于：

[[x] + p for x in seqs[0] for p in [[]] ]

这等同于所有这些：

[[x] + [] for x in seqs[0]]
[[x] for x in seqs[0]]
[[1], [2], [3]]

如果再加一个序列，比如 product([4, 5, 6], [1, 2, 3])，那么列表推导式就变成这样：

[[x] + p for x in [4, 5, 6] for p in product(*seqs[1:])]
[[x] + p for x in [4, 5, 6] for p in [[1], [2], [3]]]
[[4, 1], [4, 2], [4, 3], [5, 1], [5, 2], [5, 3], [6, 1], [6, 2], [6, 3]]

这个模式会继续下去；对于每增加一个序列，序列中的每个值都会被加到后续序列的笛卡尔积中的每个值前面。