n-мерный ход

Question

Я реализую самую длинную общую подпоследовательность для n измерений. Текущая проблема: как пройти через n строк? Простое вложение циклов for больше не будет работать, потому что мне нужно n из них. Какое хорошее решение для этой проблемы? Циклы + рекурсия, наверное, но как именно? Я не спрашиваю о полном алгоритме, а только о том, как генерировать все комбинации для алгоритма динамического программирования. Пример в 2D:

for position, char in word0:
  for position1, char1 in word1:
    # code here

Answer 1

Если вы не хотите делать это рекурсией, Вы можете реализовать n вложенные циклы "для", как это (однако, циклы "for" больше не являются буквально для циклов):

i - массив индексов.
m - это массив верхних пределов каждого i
ii является индексом i индексов (range(n))

n=4 # just an example
m=[3 for ii in range(n)] # just an example

i=[0 for ii in range(n)]
while True:
  print " ".join(["%2d"%x for x in i])
  for ii in range(n-1,-1,-1):
    i[ii] +=1
    if i[ii]<m[ii]: break # index i[ii] has not yet reached its individual max. value
    i[ii] = 0
  if sum(i)==0: break # all indices have counted to max. value 

Answer 2

Это похоже на подсчет, скажем, от 0000 до 9999, что соответствует четырем словам по десять букв каждое: 0000-> 0001-> 0002 -> ...-> 0009-> 0010 -> ...На каждом этапе вы увеличиваете последнюю цифру, а когда она переворачивается, вы увеличиваете предыдущую и т. Д. До тех пор, пока первая цифра не перевернется, и вы закончите.итератор:

def count(limits):
    idcs = [0] * len(limits)
    while True:
        yield tuple(idcs)
        for n in range(len(limits)-1, -1, -1):
            idcs[n] += 1
            if idcs[n] != limits[n]:
                break
            elif n == 0:
                raise StopIteration
            else:
                idcs[n] = 0

words = ['foo', 'bar', 'xyzzy']
for idcs in count(map(len, words)):
    chars = map(lambda w, i: w[i], words, idcs)
    print idcs, chars