python - n维遍历

Question

我正在实现 n 维的最长公共子序列。当前问题：如何遍历 n 个字符串？简单的嵌套for循环将不再起作用，因为我需要其中的 n 个。这个问题有什么好的解决方案？循环+递归，我想，但究竟如何？我不是要求完整的算法，而只是如何为动态规划算法生成所有组合。二维示例：

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

Answer 1

如果您不想通过递归来实现，您可以n像这样实现嵌套的“for”循环（尽管“for”循环不再是字面上的 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