使用递归的集合的交叉积

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

我能想到的最简单的笛卡尔积的递归定义看起来像这样.你可以看到像你一样,这有一个循环 - 实际上,两个循环嵌入在列表理解中.与您的不同,它可以处理两个或更多序列:

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

模式从那里继续; 对于每个另外的序列,序列中的每个值被预先附加到以下序列的笛卡尔积中的每个值.

Answer 2

使用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。