Python：遞歸創建條件列表的列表

Question

我想創建n個項目的所有可能的分佈。這是指通常已知的鴿子原理。

下面的值是Microsoft Excel中的結果：

get_distributions(list, number_of_items_to_distribute) 
get_distributions([], 1) = [[1]] 
get_distributions([], 2) = [[1, 1], [2]] 
get_distributions([], 3) = [[1, 1, 1], [1, 2], [2, 1], [3]] 
get_distributions([], 4) = [[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 3], [2, 1, 1], [2, 2], [3, 1], [4]] 

我已經有一些代碼，但也有一些問題，刪除臨時表。使用此功能，我可以在「end：」後打印出好的結果，但某些值（如[1,2]（調用n = 3））缺失。除此之外，這些值不會附加到我的all_distribution。

我很感興趣的方式，我試圖解決這個問題。這是一個好方法還是我絕對錯了？

Answer 1

您的代碼的主要問題是，列表all_distributions最終包含許多對同一輸入列表distribution的引用。當您撥打all_distributions.append(distribution)時，列表distribution未被複制到列表all_distributions中，但僅添加對該列表的引用。 all_distributions.append(list(distribution))

的最小修復你的代碼是插入的副本，在基本情況下刪除​​，和遞歸調用後加入distribution.pop()：

all_distributions = [] 

def get_distributions(distribution, items): 
    if items == 0: 
     all_distributions.append(list(distribution)) 
    else: 
     for i in range(1, items + 1): 
      distribution.append(i) 
      get_distributions(distribution, items - i) 
      distribution.pop() 

get_distributions([], 3) 
print(all_distributions) 

輸出您可以通過顯式地將副本解決這個問題： [[1, 1, 1], [1, 2], [2, 1], [3]]

---

一個更好的辦法是避免使用distribution.append，而是使用加運算的名單，像這樣：

def get_distributions(distribution, items): 
    if items == 0: 
     all_distributions.append(distribution) 
    else: 
     for i in range(1, items + 1): 
      d = distribution + [i] 
      get_distributions(d, items - i) 

列表上的加號運算符通過連接兩個給定列表來創建一個新列表。在這種情況下，我們將連接distribution右側的單個元素i以獲取包含distribution後跟i中的元素的新副本。

---

另一項改進是避免全局變量all_distributions，而是返回分佈的名單：

def get_distributions(distribution, items): 
    if items == 0: 
     return [distribution] 
    else: 
     all_distributions = [] 
     for i in range(1, items + 1): 
      d = distribution + [i] 
      all_distributions += get_distributions(d, items - i) 
     return all_distributions 

print(get_distributions([], 4)) 

輸出：[[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 3], [2, 1, 1], [2, 2], [3, 1], [4]]