n維遍歷

Question

我正在實現n維最長的公共子序列。目前的問題：我如何遍歷n個字符串？簡單地嵌套for循環將不再工作，因爲我需要它們中的n個。這個問題有什麼好的解決方案？循環+遞歸，我想，但究竟如何？我並不是要求完整的算法，而只是要爲動態規劃算法生成所有組合。 例2D：

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

Answer 1

這類似於計數，比方說，從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 

Answer 2

如果你不想用遞歸， 可以實現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