顯示列表中所有數字組合的算法

我將如何構建一個遞歸函數以顯示數字列表中的所有符號可能性，例如：（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

顯示列表中所有數字組合的算法

回答

相關問題