7

我编写了以下递归例程来计算两组的叉积。

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。

4

2 回答 2

9

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

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

模式从那里继续；对于每个附加序列，序列中的每个值都被附加到以下序列的笛卡尔积中的每个值之前。

于 2013-02-27T00:34:03.453 回答
2

使用迭代工具

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。

于 2013-02-26T21:35:12.750 回答