使用递归的集合的叉积 [英] Cross product of sets using recursion

问题描述

我编写了以下递归例程来计算两个集合的叉积.

I wrote the following recursive routine to compute cross product of two sets.

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 中的循环并尝试在相同的函数中执行.我正在寻找解决问题的不同方法.

Is it possible to make the recursion better, for example removing the loop in else and trying to do in same function. I'm looking at different ways of solving the problem.

不是在寻找具有内置功能的解决方案.寻找如何以不同的方式进行递归，而不是使用 itertools.product.

Not looking for a solution with something in-built. Looking for how can I do recursion differently, and not use itertools.product.

推荐答案

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

The simplest recursive definition of the cartesian product I can think of looks like this. You can see that like yours, this has a loop -- actually, two loops embedded in a list comprehension. Unlike yours, this can handle two or more sequences:

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

这是一个演练，让您了解它是如何工作的.根据定义，空序列的笛卡尔积 (product()) 是包含空序列的序列.换句话说，product() == [[]] -- 见在这里为什么.

Here's a walk-through to give you a sense of how it works. By definition, the cartesian product of an empty sequence (product()) is a sequence containing the empty sequence. In other words, product() == [[]] -- see here for why.

现在假设我们调用 product([1, 2, 3]) -- seqs 是非空的，所以返回值是列表的结果理解.在这种情况下，product(*seqs[1:]) == product(*[]) == product() == [[]]，所以列表推导等价于:

Now let's say we call product([1, 2, 3]) -- seqs is non-empty, so the return value is the result of the list comprehension. In this case, product(*seqs[1:]) == product(*[]) == product() == [[]], so the list comprehension is equivalent to this:

[[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]).现在列表推导式如下所示:

Adding another sequence, we have product([4, 5, 6], [1, 2, 3]). Now the list comprehension looks like this:

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

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

The pattern continues from there; for each additional sequence, each of the values in the sequence is prepended to each of the values in the cartesian product of the following sequences.

这篇关于使用递归的集合的叉积的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！