Project Euler # 18 – как перебрать все возможные пути в древовидной структуре с помощью Python?
Я пытаюсь изучить Python на атлантическом пути и застрял в Project Euler # 18.
Весь материал, который я могу найти в Интернете (и есть еще много ошибок в googling, которые произошли за пределами этого), есть некоторые вариации на «хорошо, вы МОЖЕТЕ использовать его, но вот более элегантное решение» …
- Python: закрытие цикла for путем чтения stdout
- Выход выполнения команды Python
- чтение строк 2 за раз
- Как вручную разобрать исходящий адрес GAE?
- Нормализовать массив в 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).
- Объединение нескольких итераторов с помощью ключа
- Как слить два кортежа в Python?
- Как конструкторы производных классов работают в python?
- Изменения в Python после погружения в Python
- Лучшая среда разработки с открытым исходным кодом для создания приложений в Google App Engine?
One Solution collect form web for “Project Euler # 18 – как перебрать все возможные пути в древовидной структуре с помощью Python?”
Здесь проще использовать рекурсию:
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]]
Здесь идея состоит в том, что all_paths(r, c) возвращают все пути, начиная с строки r , столбец c , который обычно получается путем рекурсивного переноса всех путей из обоих узлов ниже него и добавления текущего элемента ко всем из них.
Если мы находимся в последней строке, мы просто возвращаем путь, состоящий из одного элемента.
Чтобы получить все пути, начинающиеся с вершины, вызовите all_paths(0, 0) .
Затем эту функцию можно легко изменить, чтобы возвращать суммы каждого пути, а не сами пути, и с последующей модификацией он может возвращать только самую большую сумму, а не все из них. «Правильный способ» решения этой проблемы – это, по сути, лишь мемуаризованная версия этого.