显示列表中所有数字组合的算法

我将如何构建一个递归函数以显示数字列表中的所有符号可能性，例如：（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）

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

我尝试了几种不同的方法，包括尝试修改其他类似问题的代码，但其中大部分包括更改列表本身。

谢谢！

来源

2013-04-18 Akira Iris

好像你正在过滤5！组合，他们每个人可能会翻转他们的位。考虑翻转五位 - 将需要多少步才能将它们全部打开，并且如何按逻辑来处理它？ – Makoto 2013-04-18 03:56:29

@Makoto不，不包括组合的阶乘。这是一个简单的指数（2^5）阐述。 – RBarryYoung 2013-04-18 04:02:30

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

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

在递归的情况下，函数做了一点工作以使自己更接近目标，然后递归地调用自己以完成剩下的工作。

下面是一个方法来分解你的问题的递归函数。

在递归的情况下，“少许工作”是将列表中的一个数字的符号设置为正数，并且也是以将该数字的符号设置为负数。我们需要在两次分配后进行递归，因为我们需要为每个符号生成组合。

在基本情况下，所有的数字都有自己的标志设置，所以我们只是打印数字列表。例如，在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-18 04:38:43

+1为谈论“算法”部分的问题（而不是一些示例可能的实现...） – heltonbiker 2013-04-18 04:43:45

谢谢！这个解释非常好，现在它实际上变得更有意义了，并且代码正如我所需要的那样工作（我在C＃中完成了它）。 – 2013-04-18 15:14:18

生成所有可能的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]。现在，对于每个列表，请执行以下操作。

如果在列表中有第1个位置，则将原始列表中的该位置的数字替换为负数。

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

来源

2013-04-18 04:08:55 Dilawar

我建议用'-1'来代替零来生成这些列表。然后，您可以将元素明智地乘以列表。 – heltonbiker 2013-04-18 04:11:38

大厦，我提供了一个（重）Python的实现（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-18 04:24:33 heltonbiker

显示列表中所有数字组合的算法

回答

相关问题