Учитывая tree
tree = \
[ [1]
, [2, 3]
, [4, 5, 6]
, [7, 8, 9, 10]
, [11, 12, 13, 14, 15]
]
И traverse функцию
def traverse (tree):
def loop (path, t = None, *rest):
if not rest:
for x in t:
yield path + [x]
else:
for x in t:
yield from loop (path + [x], *rest)
return loop ([], *tree)
Пройти все пути ...
for path in traverse (tree):
print (path)
# [ 1, 2, 4, 7, 11 ]
# [ 1, 2, 4, 7, 12 ]
# [ 1, 2, 4, 7, 13 ]
# [ 1, 2, 4, 7, 14 ]
# [ 1, 2, 4, 7, 15 ]
# [ 1, 2, 4, 8, 11 ]
# [ 1, 2, 4, 8, 12 ]
# ...
# [ 1, 3, 6, 9, 15 ]
# [ 1, 3, 6, 10, 11 ]
# [ 1, 3, 6, 10, 12 ]
# [ 1, 3, 6, 10, 13 ]
# [ 1, 3, 6, 10, 14 ]
# [ 1, 3, 6, 10, 15 ]
Или собрать всепутей в списке
print (list (traverse (tree)))
# [ [ 1, 2, 4, 7, 11 ]
# , [ 1, 2, 4, 7, 12 ]
# , [ 1, 2, 4, 7, 13 ]
# , [ 1, 2, 4, 7, 14 ]
# , [ 1, 2, 4, 7, 15 ]
# , [ 1, 2, 4, 8, 11 ]
# , [ 1, 2, 4, 8, 12 ]
# , ...
# , [ 1, 3, 6, 9, 15 ]
# , [ 1, 3, 6, 10, 11 ]
# , [ 1, 3, 6, 10, 12 ]
# , [ 1, 3, 6, 10, 13 ]
# , [ 1, 3, 6, 10, 14 ]
# , [ 1, 3, 6, 10, 15 ]
# ]
Выше мы использовали генераторы, которые являются высокоуровневой функцией в Python.Может быть, вы хотите понять, как реализовать решение с использованием более примитивных функций ...
Общий механизм, который мы ищем здесь, - это монада списка, которая отражает идею неоднозначных вычислений;некоторая процедура, которая может потенциально возвратить более чем одно значение.
Python уже предоставляет списки и способ их построения с использованием [].Нам нужно только предоставить операцию привязки с именем flat_map ниже
def flat_map (f, xs):
return [ y for x in xs for y in f (x) ]
def traverse (tree):
def loop (path, t = None, *rest):
if not rest:
return map (lambda x: path + [x], t)
else:
return flat_map (lambda x: loop (path + [x], *rest), t)
return loop ([], *tree)
print (traverse (tree))
# [ [ 1, 2, 4, 7, 11 ]
# , [ 1, 2, 4, 7, 12 ]
# , [ 1, 2, 4, 7, 13 ]
# , ... same output as above ...
# ]
Oh, а в Python есть встроенная функция product, которая работает точно так, как нам нужно.Разница лишь в том, что пути будут выводиться в виде кортежей () вместо списков []
from itertools import product
tree = \
[ [1]
, [2, 3]
, [4, 5, 6]
, [7, 8, 9, 10]
, [11, 12, 13, 14, 15]
]
for path in product (*tree):
print (path)
# (1, 2, 4, 7, 11)
# (1, 2, 4, 7, 12)
# (1, 2, 4, 7, 13)
# (1, 2, 4, 7, 14)
# (1, 2, 4, 7, 15)
# ... same output as above ...
В вашей программе вы пытаетесь абстрагировать этот механизм с помощью различных классов, node и edgeи diagraph.В конечном итоге вы можете структурировать свою программу так, как вам хочется, но знайте, что не нужно, чтобы было более сложным, чем мы ее здесь написали.
Обновление
Как указывает @ user3386109 в комментариях, моя программа выше генерирует пути, как если бы каждый родитель был подключен к всем дочерним элементам.Однако это ошибка, поскольку ваш график показывает, что родители подключены только к смежным детям.Мы можем исправить это с помощью модификации нашей программы - изменения ниже полужирный
def traverse (tree):
def loop (path, <b>i,</b> t = None, *rest):
if not rest:
for <b>(j,</b>x<b>)</b> in <b>enumerate (</b>t<b>)</b>:
<b>if i == j or i + 1 == j:</b>
yield path + [x]
else:
for <b>(j,</b>x<b>)</b> in <b>enumerate (</b>t<b>)</b>:
<b>if i == j or i + 1 == j:</b>
yield from loop (path + [x], <b>j,</b> *rest)
return loop ([], <b>0,</b> *tree)
Выше мы используем индексы i и j, чтобы определить, какие узлы являются "смежными"но это загромождало нашу loop кучу.Кроме того, новый код выглядит так, как будто вводит некоторое дублирование.Придавая этому намерению имя adjacencies, мы сохраняем чистоту нашей функции
def traverse (tree):
<b>def adjacencies (t, i):
for (j, x) in enumerate (t):
if i == j or i + 1 == j:
yield (j, x)</b>
def loop (path, i, t = None, *rest):
if not rest:
for <b>(_, x)</b> in <b>adjacencies (t, i)</b>:
yield path + [x]
else:
for <b>(j, x)</b> in <b>adjacencies (t, i)</b>:
yield from loop (path + [x], j, *rest)
return loop ([], 0, *tree)
То же самое, но на этот раз мы получим результат, указанный в исходном вопросе
for path in traverse (tree):
print (path)
# [1, 2, 4, 7, 11]
# [1, 2, 4, 7, 12]
# [1, 2, 4, 8, 12]
# [1, 2, 4, 8, 13]
# [1, 2, 5, 8, 12]
# [1, 2, 5, 8, 13]
# [1, 2, 5, 9, 13]
# [1, 2, 5, 9, 14]
# [1, 3, 5, 8, 12]
# [1, 3, 5, 8, 13]
# [1, 3, 5, 9, 13]
# [1, 3, 5, 9, 14]
# [1, 3, 6, 9, 13]
# [1, 3, 6, 9, 14]
# [1, 3, 6, 10, 14]
# [1, 3, 6, 10, 15]
ПричинаЭта простая функция adjancies работает потому, что ваши входные данные единообразны и действительны.Вы можете четко визуализировать индексы i и i + 1, используя цветовое кодирование путей в вашем изображении.Нам никогда не нужно беспокоиться об ошибке индекса за пределами границ, поскольку вы можете видеть, что i + 1 никогда не вычисляется на узлах без дочерних элементов (т. Е. В последней строке).Если вы указали неверные данные, traverse не гарантирует действительный результат.
