Project Euler # 18 – как перебрать все возможные пути в древовидной структуре с помощью Python?

Я пытаюсь изучить Python на атлантическом пути и застрял в Project Euler # 18.

Весь материал, который я могу найти в Интернете (и есть еще много ошибок в googling, которые произошли за пределами этого), есть некоторые вариации на «хорошо, вы МОЖЕТЕ использовать его, но вот более элегантное решение» …

• Как я могу получить значения локалей функции после ее выполнения?
• подчеркивание питона
• Обработка ошибок Переменные в программе калькулятора, номера обработки ошибок в порядке
• Как включить сторонние библиотеки Python в Google App Engine?
• метки полосы python

Я понимаю, я полностью это делаю. Есть действительно опрятные решения, и я с нетерпением жду того дня, когда фраза «ациклический граф» вызывает в голове что-то большее, чем мутное, 1 мегапиксельное разрешение в моей голове. Но мне нужно идти, прежде чем я забегу сюда, посмотрю состояние и поиграю с грубым ответом.

Итак, вопрос: как я могу генерировать (перечислять?) Все допустимые пути для треугольника в Project Euler # 18 и хранить их в соответствующей структуре данных python? (Список списков – это моя первоначальная наклонность?). Я не хочу ответа – я хочу знать, как перебирать все пути и хранить их в структуре данных.

Вот что у меня есть. Я определенно ошибаюсь в том, что набор данных ошибочен. Желаемое поведение заключалось бы в том, чтобы сначала «глубина» (?) », А не просто цикл по каждой строке неэффективно. Я читаю ч. 3 книги Норвига, но не смог перевести psuedo-код. Пробовал читать библиотеку python AIMA для ch. 3, но он делает слишком много прыжков.

triangle = [ [75], [95, 64], [17, 47, 82], [18, 35, 87, 10], [20, 4, 82, 47, 65], [19, 1, 23, 75, 3, 34], [88, 2, 77, 73, 7, 63, 67], [99, 65, 4, 28, 6, 16, 70, 92], [41, 41, 26, 56, 83, 40, 80, 70, 33], [41, 48, 72, 33, 47, 32, 37, 16, 94, 29], [53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14], [70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57], [91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48], [63, 66, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31], [04, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23], ] def expand_node(r, c): return [[r+1,c+0],[r+1,c+1]] all_paths = [] my_path = [] for i in xrange(0, len(triangle)): for j in xrange(0, len(triangle[i])): print 'row ', i, ' and col ', j, ' value is ', triangle[i][j] ??my_path = somehow chain these together??? if my_path not in all_paths all_paths.append(my_path) 

Ответы, которые предпочитают внешние библиотеки (например, itertools).

 def all_paths(r, c): current = triangle[r][c] if r < len(triangle) - 1: below_paths = all_paths(r+1, c) + all_paths(r+1, c+1) return [[current] + path for path in below_paths] else: return [[current]]