在Python中爲嵌套循環創建遞歸函數

Question

我發佈了這個問題： Non overlapping pattern matching with gap constraint in python;兩個月前。我只得到一個迴應。但解決方案非常長，並且對於模式中的每個單詞，都會形成一個嵌套循環。有什麼辦法遞歸形成下面的函數嗎？

i=0 
while i < len(pt_dic[pt_split[0]]): 
    match=False 
    ii = pt_dic[pt_split[0]][i] 
    #print "ii=" + str(ii) 

    # Start loop at next index after ii 
    j = next(x[0] for x in enumerate(pt_dic[pt_split[1]]) if x[1] > ii) 
    while j < len(pt_dic[pt_split[1]]) and not match: 
     jj = pt_dic[pt_split[1]][j] 
     #print "jj=" + str(jj) 
     if jj > ii and jj <= ii + 2: 

      # Start loop at next index after ii 
      k = next(x[0] for x in enumerate(pt_dic[pt_split[2]]) if x[1] > jj) 
      while k < len(pt_dic[pt_split[2]]) and not match: 
       kk = pt_dic[pt_split[2]][k] 
       #print "kk=" + str(kk) 
       if kk > jj and kk <= jj + 2: 

        # Start loop at next index after kk 
        l = next(x[0] for x in enumerate(pt_dic[pt_split[3]]) if x[1] > kk) 
        while l < len(pt_dic[pt_split[2]]) and not match: 
         ll = pt_dic[pt_split[3]][l] 
         #print "ll=" + str(ll) 
         if ll > kk and ll <= kk + 2: 
          print "Match: (" + str(ii) + "," + str(jj) + "," + str(kk) + "," + str(ll) + ")" 
          # Now that we've found a match, skip indices within that match. 
          i = next(x[0] for x in enumerate(pt_dic[pt_split[0]]) if x[1] > ll) 
          i -= 1 
          match=True 
         l += 1 
      k += 1 
     j += 1 
    i += 1 

編輯：對於那些誰沒有得到上下文：

我想找到總沒有。的出現在序列中的模式的非重疊匹配，其中間隙約束2.

例如， A B C是使用某種算法找到的模式。我必須找到出現在如A A B B C D E A B C …這樣的序列中的這個圖案的總數，其中最大間隙約束是2.

最大。在序列中沒有看到間隙，但是在屬於序列中的子串的模式的兩個單詞之間可以看到間隙。例如。 Pat: A B C和seq: A B D E C B A B A B C D E。

在這種情況下，A B D E C ...與A，B和B，C之間允許的最大兩個間隙匹配。接下來我們找到A B A B C作爲另一個匹配。有趣的是。有兩個匹配，（2個字符b/w A，B和2個字符b/w B，C）。但是，我們只會將它計爲一個，因爲它是重疊匹配。 A B X X X C無效。

Answer 1

我只簡單地讀過原始問題。我真的不確定我的差距是否合適。我覺得你爲L分類代碼搜索唯一索引的順序和與L型元件全部名單，其中第N個元素是第N序列，且其中兩個相鄰項目滿足條件prev < next < prev + GAP + 1

反正這個問題是關於嵌套的循環。

以下代碼的基本思想是將序列列表傳遞給遞歸函數。這個函數接受它的第一個序列並遍歷它。剩下的序列被傳遞給相同函數的其他實例，其中每個實例都執行相同的操作，即迭代第一個序列並傳遞其餘的序列，直到剩下的序列不會被迭代爲止。

在此過程中，部分解決方案正在逐步構建。只有當這個部分解決方案滿足條件時，遞歸纔會繼續。當所有序列都耗盡時，部分解決方案成爲最終解決方案。

list_of_seqs= [ 
    [0, 1, 7, 11, 22, 29], 
    [2, 3, 8, 14, 25, 33], 
    [4, 9, 15, 16, 27, 34], 
] 


def found_match(m): 
    print(m) 

GAP = 2 
def recloop(part, ls): 
    if not ls: 
     found_match(part) 
     return 
    seq, *ls = ls # this is Python3 syntax 
    last = part[-1] if part else None 
    # this is not optimized: 
    for i in seq: 
     if last is None or last < i <= last + GAP + 1: 
      recloop(part + [i], ls) 

recloop([], list_of_seqs) 

對於Python2與seq, ls = ls[0], ls[1:]