Сложите детские дорожки

Question

Это более общий вопрос программирования / парадигмы / алгоритма, но я изложу его, используя python.

Учитывая следующую структуру данных:

• a является элементом типа T
• a имеет перечисляемое свойство под названием children с элементами типа T

Как мне сложить эту структуру данных, чтобы получить все пути из начального элемента?

Чтобы проиллюстрировать проблему дальше, позвольте мне уточнить

c = {
'children': []
}
b = {
'children': [c]
}
a = {
'children': [b]
}

fold_from_start(a) => [[a, b, c]]

Эта функция должна вычислить все пути из a. Если мы расширим предыдущее примерно так:

d = {
'children': []
}
b['children'] = [c, d]

fold_from_start(a) => [[a, b, c], [a, b, d]]

До сих пор я придумал следующий код, использующий рекурсивную конструкцию:

def fold_from_start(start, path, paths):
    if not len(start['children']):
        paths.append(path)  # leaf element
    else:
        new_path = path.copy()
        new_path.append(start)
        for child in start['children']:
            fold_from_start(child, new_path, paths)

, который можно назвать так:

paths = []
fold_from_start(a, [a], paths)

К сожалению, это дает

[a, a, b]
[a, a, b]

Я знаю, что раньше видел этот код в учебнике, но, к сожалению, я не могу придумать, как это делается. Какова очевидная проблема в этой функции, которую я склонен упускать из виду?

Answer 1

Это было всего несколько мелких ошибок. Это работает:

c = {
'name' : 'c',
'children': []
}
b = {
'name' : 'b',
'children': [c]
}
a = {
'name' : 'a',
'children': [b]
}
d = {
'name' : 'd',
'children': []
}
b['children'] = [c, d]

def fold_from_start(start, path, paths):
    new_path = path.copy()
    new_path.append(start['name'])
    if len(start['children']) == 0:
        paths.append(new_path)  # leaf element
    else:
        for child in start['children']:
            fold_from_start(child, new_path, paths)

paths=[]
fold_from_start(a, [], paths)
print(str(paths))

Вам также нужно добавить листовой узел к текущему пути. Но поскольку вы не хотите добавлять его в переменную пути вызывающей стороны, вы сначала копируете.