条件下的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))