Возвращающиеся ветви дерева как списки в 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]] 

Изображение для второго примера

Изображение для третьего примера

Вот код, я написал, что работает только для т он первый пример, это ужасно, и мне действительно стыдно за это:/Я пробовал десятки подходов, используя классы и генераторы, но я не очень хорошо знаком с ними, и код вернул половину параметров даже для первого примера.

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