在Python中返回樹的分支作爲列表

Question

我試圖在Python中編寫一個遞歸函數，該函數返回樹的分支作爲列表，給定分支的深度或max_sum。我非常沮喪。也許有類或發生器更容易的實現？以下是我想要實現的功能行爲的詳細說明。

func(data, depth) 
'''Accepts a list with numbers > 0 and depth, i.e. max elements per list; 
    returns each branch of a tree'''  

----------Examples-------------- 
Input: func([2, 1], depth=2) 
Output: [[2, 2], [2, 1], [1, 2], [1, 1]] 

Input: func([3, 2, 1], depth=2) 
Output: [[3, 3], [3, 2], [3, 1] 
     [2, 3], [2, 2], [2, 1] 
     [1, 3], [1, 2], [1, 1]] 

Input: func([2, 1], depth=3) 
Output: [[2, 2, 2], [2, 2, 1], [2, 1, 2], [2, 1, 1], 
     [1, 2, 2], [1, 2, 1], [1, 1, 2], [1, 1, 1]] 

圖片爲第二個例子

圖片爲第三個例子

下面是我寫的代碼，只在t工作他第一個例子很糟糕，我真的感到很慚愧：/我嘗試了幾十種使用類和生成器的方法，但我對這些方法不是很熟悉，即使對於第一個示例，代碼也只返回了一半選項。

tree = [] 
node_list = [2, 1] 

def make_branch(depth=2, branch=None, d={0:2, 1:1}, switch=False, count=0): 
    #print(count) 

    if branch is None: 
     branch = [] 

    for i in range(2): 
     #print(i) 
     if switch: 
      branch.append(d[i+1]) 
      switch=False 
     else: 
      branch.append(d[i]) 

     if len(branch) >= depth: 
      tree.append(branch) 
      print(branch) 
      return 

     make_branch(count= count + 1, branch=branch) 
     #print(-count) 
     branch = branch[:-1] 


for i in range(len(node_list)): 
    if i % 2 == 0: 
     make_branch() 
    else: 
     make_branch(switch=True) 

print(tree) 

Answer 1

我不明白你爲什麼想把它和遍歷一棵樹聯繫起來。你的任務基本上只是生成所有排列（帶替換） - 這與具有固定集合的笛卡爾產品相同 - 在一組數字上給定長度。

在Python中，你可以如下做到這一點：

import itertools 
for i in itertools.product([1,2], repeat=3): 
    print i 

這將如輸出你的第三個例子。請注意，每個輸出都是一個元組而不是一個列表 - 所以你可能想要轉換它們。

最簡單的實現可能會像這樣工作：

def prod(lst, depth, buf=''): 
    if depth == 0: 
     print buf 
     return 
    for elem in lst: 
     prod(lst, depth - 1, buf + str(elem)) 

prod([1,2], 3) 
print 
prod([1,2,3], 2) 

輸出：

111 
112 
121 
122 
211 
212 
221 
222 

11 
12 
13 
21 
22 
23 
31 
32 
33