使用递归计算集合的交叉积

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。

- gizgok

---

你知道itertools.product吗？ - Pavel Anossov

我认为你最后的 combine 调用需要在前面加上 return。 - DSM

您能否解释一下为什么您需要一个递归解决方案？这还不清楚。 - Udo Klein

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

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

- senderle

---

谢谢你。我使用了你的实现在这里来进行C++编译时的向量叉积，仅供自娱自乐。 - Yakk - Adam Nevraumont

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

product函数中的n是您传递给它的参数数量。

- Udo Klein

---

这完全错过了 OP 的点，即如何改进递归。 - tacaswell

@tcaswell：公平地说，原始版本中说“我正在寻找解决问题的不同方法”，并没有包含最后一段，所以当时这是有意义的。 - DSM