爲什麼這個遞歸函數在達到基本情況時永不結束？

Question

所以我試圖按照這個烏爾曼的算法來解決子圖同構問題，通過阻止它在Python上。它說在找到兼容矩陣時停止算法，但是我的代碼不斷打印找到的其餘矩陣，即使它達到基本情況。我究竟做錯了什麼？

recurse(used_columns, cur_row, G, P, M) 
    if cur_row = num_rows(M) 
     if M is an isomorphism: 
      output yes and end the algorithm 

    for all unused columns c 
     set column c in M' to 1 and other columns to 0 
     mark c as used 
     recurse(used_column, cur_row+1, G, P, M') 
     mark c as unused 

    output no 

這是我如何編碼它：

def permute(m0,row,h,g): 
    if(row==len(m0)-1): 
     n=0 
     for i in range(len(m0[0])): 
      for j in range(len(m0)): 
       n+=m0[j][i] 
      if(n>1): 
       return 
      n=0 
     res=[[sum(a*b for a,b in zip(m0_row,h_col)) for h_col in zip(*h)] for m0_row in m0] 
     resTr=[[res[j][i] for j in range(len(res))] for i in range(len(res[0]))] 
     arr=[[sum(a*b for a,b in zip(m0_row,resTr_col)) for resTr_col in zip(*resTr)] for m0_row in m0] 
     for row in arr: 
      print(row) 
     if(g==arr): 
      print("YES!") 
      return 
    for n in range(len(m0[0])): 
     m0[row][n]=0 
    for n in range(len(m0[0])): 
     m0[row][n]=1 #mark c as used 
     permute(m0,row+1,h,g)  
     m0[row][n]=0 #mark c as unused 
    print("No") 
    return 

這是輸出：

[0, 0, 1] 

[0, 0, 1] 

[1, 1, 0] 

YES! 

[0, 0, 1] 

[0, 0, 1] 

[1, 1, 0] 

YES! 

No 

No 

[0, 0, 1] 

[0, 0, 1] 

[1, 1, 0] 

YES! 

[0, 0, 1] 

[0, 0, 1] 

[1, 1, 0] 

YES! 

No 

[0, 0, 1] 

[0, 0, 1] 

[1, 1, 0] 

YES! 

[0, 0, 1] 

[0, 0, 1] 

[1, 1, 0] 

YES! 

No 

No 

我只是想打印的第一次出現真正停止，並打印「否「，當找不到相同的矩陣時。誰能幫忙？

Answer 1

您沒有任何退出條件。 Python不關心你打印「YES！」所以利用返回值變得必要。算法結束時應返回True，否則返回False。此外，還必須檢查此值時，函數調用自身（最終for環路），並沿True值傳遞，所以它會立即停止：

def permute(m0,row,h,g): 
    if(row==len(m0)-1): 
     n=0 
     for i in range(len(m0[0])): 
      for j in range(len(m0)): 
       n+=m0[j][i] 
      if(n>1): 
       return False 
      n=0 
     res=[[sum(a*b for a,b in zip(m0_row,h_col)) for h_col in zip(*h)] for m0_row in m0] 
     resTr=[[res[j][i] for j in range(len(res))] for i in range(len(res[0]))] 
     arr=[[sum(a*b for a,b in zip(m0_row,resTr_col)) for resTr_col in zip(*resTr)] for m0_row in m0] 
     for row in arr: 
      print(row) 
     if(g==arr): 
      print("YES!") 
      return True 
    for n in range(len(m0[0])): 
     m0[row][n]=0 
    for n in range(len(m0[0])): 
     m0[row][n]=1 #mark c as used 
     if permute(m0,row+1,h,g): #exit when finished 
      return True  
     m0[row][n]=0 #mark c as unused 
    print("No") 
    return False 

另外，如果你想以後在實際使用的輸出你的程序;您可以返回該變量而不是True，向下傳遞該值，否則返回None。這個改變會很小，新的最終for循環會變成這樣：

for n in range(len(m0[0])): 
    m0[row][n]=1 #mark c as used 
    out=permute(m0,row+1,h,g) 
    if out: #exit when finished 
     return out 
    m0[row][n]=0 #mark c as unused