條件下的Python置換（回溯）

Question

我想用回溯來解決問題。正如...我給出了一個數字列表，我想使用回溯來找到尊重給定條件的所有可能的排列組合。

我有用於生成排列列表的代碼，但它沒有幫助，因爲我無法在將每個排列添加到列表之前單獨檢查每個排列，因此它不是回溯，它只是遞歸。 我也明白回溯作品的方式：從0到x，但不是一個列表排列...

這是我的置換列表生成

def permutare(self, lista): 
     if len(lista) == 1: 
      return [lista] 
     res = [] 
     for permutation in self.permutare(lista[1:]): 
      for i in range(len(lista)): 
       res.append(permutation[:i] + lista[0:1] + permutation[i:]) 
     return res 

作品而不是我的幫助。我嘗試在那裏插入驗證，但無處可用..我嘗試了所有我能找到的排列算法。我需要一個回溯

任何想法/算法/僞代碼的條件回溯排列？

Answer 1

以下是通過交換列表中的元素來使用回溯的解決方案。

的基本思想是：

• 交換的每個元素到起動位置。
• 計算剩餘與索引分區[0：啓動]固定

代碼：

def swap(lista, idx1, idx2): 
    temp = lista[idx1] 
    lista[idx1] = lista[idx2] 
    lista[idx2] = temp 

def valid(): 
    return True 

def permutare(lista, start): 
    if start >= len(lista): 
     if valid(): 
      return [list(lista)] 

    output = [] 
    for idx in xrange(start, len(lista)): 
     swap(lista, start, idx) 
     output.extend(permutare(lista, start + 1)) 
     swap(lista, start, idx) # backtrack 
    return output 

print len(permutare(['a','b','c'], 0))