Как создать список всех возможных списков, удовлетворяющих определенному условию?

В настоящее время я пытаюсь выполнить проект Euler problem 18 ( https://projecteuler.net/problem=18 ), используя метод «грубой силы» для проверки всех возможных путей. Я только что пытался использовать меньший треугольник «модели». Я использовал понимание списка, чтобы создать список списков, где внутренние списки будут содержать индексы для этой строки, например:

lst = [[a,b,c,d] for a in [0] for b in [0,1] for c in [0,1,2] for d in [0,1,2,3] if b == a or b == a + 1 if c == b or c == b + 1 if d == c or d == c + 1] 

Это дает мне список списков, которые я хочу, а именно:

 [[0,0,0,0],[0,0,0,1],[0,0,1,1],[0,0,1,2],[0,1,1,1],[0,1,1,2],[0,1,2,2], [0,1,2,3]] 

Примечание: условия if гарантируют, что он перемещается только к соседним номерам в следующей строке треугольника, так что

 lst[i][j] = lst[i][j-1] or lst[i][j] = lst[i][j]-1 

После того, как я дошел до этого момента, я намеревался, что для каждого из внутренних списков я буду брать числа, связанные с этими индексами (поэтому [0,0,0,0] будет 3,7,2,8) и сумма их, и таким образом получить все возможные суммы, а затем взять максимум этих.

Проблема в том, что если бы я масштабировал это до большого треугольника, у меня было бы пятнадцать «за» и «если бы в моем понимании списка. Кажется, должен быть более простой способ! Я довольно новичок в Python, поэтому, надеюсь, есть некоторые очевидные возможности, которые я могу использовать, которые я пропустил до сих пор!

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

 import itertools import numpy as np # Here is the input triangle tri = np.array([[3],[7,4],[2,4,6],[8,5,9,3]]) indices = np.array([range(len(i)) for i in tri]) # Generate all the possible combinations indexCombs = list(itertools.product(*indices)) # Generate the difference between indices in successive rows for each combination diffCombs = [np.array(i[1:]) - np.array(i[:-1]) for i in indexCombs] # The only combinations that are valid are when successive row indices differ by 1 or 0 validCombs = [indexCombs[i] for i in range(len(indexCombs)) if np.all(diffCombs[i]**2<=1)] # Now get the actual values from the triangle for each row combination valueCombs = [[tri[i][j[i]] for i in range(len(tri))] for j in validCombs] # Find the sum for each combination sums = np.sum(valueCombs, axis=1) # Print the information pertaining to the largest sum print 'Highest sum: {0}'.format(sums.max()) print 'Combination: {0}'.format(valueCombs[sums.argmax()]) print 'Row indices: {0}'.format(indexCombs[sums.argmax()]) 

Выход:

Максимальная сумма: 23

Комбинация: [3, 7, 4, 9]

Индексы строк: (0, 0, 1, 0)

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