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).
- Самый эффективный метод получения ключа для значения в dict
- setup.py и добавление файла в / bin /
- Как создать фиксацию и нажать на репо с GitHub API v3?
- Есть ли простой способ в Python создать файл, который можно записать в один поток и прочитать в другом?
- Найти подпоследовательности строк в строках
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)
.
Затем эту функцию можно легко изменить, чтобы возвращать суммы каждого пути, а не сами пути, и с последующей модификацией он может возвращать только самую большую сумму, а не все из них. «Правильный способ» решения этой проблемы – это, по сути, лишь мемуаризованная версия этого.
- Удалить строки из списка, содержащего числа в python
- скрипт python для конкатенации всех файлов в каталоге в один файл
- Справочный вопрос в приложении Engine db.model
- Удаление обратных косых черт из строки
- Как записать имена, начинающиеся с A - L, в один файл, а остальные - на другой?
- Числа Фибоначчи с memoization медленны в Python?
- Использование self. * В качестве значения по умолчанию для метода
- db.ReferenceProperty () vs ndb.KeyProperty в приложении Engine
- Получить координаты местоположения с помощью bing или google API в python
- Сельдерей - Получить идентификатор задачи для текущей задачи
- Удаленная отладка на pycharm
- Пустой ответ на Facebook Graph