2

我将如何构建一个递归函数来显示数字列表中符号的所有可能性，例如（5、3、12、9、15）。列表不会改变，只是每个数字的符号。

例如，结果将是：
(-5, 3, 12, 9, 15)
(-5, -3, 12, 9, 15)
(-5, -3, -12, 9, 15)
(-5 , -3, -12, -9, 15)

以此类推，直到显示此列表的所有组合。

我尝试了几种不同的方法，包括尝试从此处的其他类似问题中调整代码，但其中大多数都包括更改列表本身。

谢谢！

4

3 回答 3

5

生成所有可能的 5 元素二进制列表，例如[0,0,0,0,0], [0,0,0,0,1], [0,0,0,1,0] .. [1,1,0,0,1] ... [1,1,1,1,1]. 现在，对于这些列表中的每一个，请执行以下操作。

如果列表中第 x 位置有 1，则用原始列表中的负数替换该位置的数字。

现在的问题是：如何递归地生成所有 5 个布尔数字的列表（二叉树？）。

于 2013-04-18T04:08:55.087 回答
3

实现递归函数时，需要考虑两种情况：基本情况和递归情况。

在基本情况下，函数不会递归调用自身。在这种情况下它可能会做一些工作，或者它可能什么都不做，因为所有的工作都已经完成了。

在递归的情况下，该函数会做一些工作以使自己更接近目标，然后递归地调用自己以完成其余的工作。

这是一种解决递归函数问题的方法。

在递归情况下，“一点工作”是将列表中一个数字的符号设置为正数，并将该数的符号设置为负数。我们需要在两个赋值之后递归，因为我们需要为每个符号生成组合。

在基本情况下，所有数字都设置了符号，所以我们只打印数字列表。

例如，在 Python 中，我们可以首先设置函数以获取数字列表，以及需要其符号集的下一个数字的索引。首先，下一个数字是列表中的第一个数字，在索引 0 处：

def allSignCombinations(numbers, nextNumberIndex=0):

基本情况发生在nextNumberIndex等于 时len(numbers)，这意味着没有数字需要设置它们的符号：

    if nextNumberIndex == len(numbers):
        print numbers

否则，我们会做“一点点工作”。我们将下一个数字的符号设置为正数和负数，并对每个符号进行递归。当我们递归时，我们告诉下一个调用从列表中的下一个数字开始工作，如果有的话：

    else:
        numbers[nextNumberIndex] = abs(numbers[nextNumberIndex])
        allSignCombinations(numbers, nextNumberIndex + 1)
        numbers[nextNumberIndex] = -numbers[nextNumberIndex]
        allSignCombinations(numbers, nextNumberIndex + 1)
于 2013-04-18T04:38:43.887 回答
2

基于 Dilawar 的回答，我提供了一个（大量）pythonic 实现（Python 语言）：

numbers = (5, 3, 12, 9, 15)

for n in range(2**len(numbers)):   # for all possible combinations (power of two)
    binrep = bin(n)[2:]            # get the binary representation as string
    binstring = str(binrep).ljust(5,'0')   # pad with left zeros
    binlist = map(int, reversed([c for c in binstring]))  # convert to a list of integers
    # apply element-wise multiplication with transformed (0,1) => (-1,1)
    print [numbers[n] * (binlist[n]*2 -1) for n in range(len(numbers))]
于 2013-04-18T04:24:33.893 回答