全排列

递归实现：把元素换到数组首位，剩下的部分做全排列

def constraint():return Truedef bound():return Truedef perm_backtracking(depth,lst):size = len(lst)if depth == size:print(lst)else:for i in range(depth,size):if constraint() and bound():lst[depth],lst[i] = lst[i],lst[depth]perm_backtracking(depth+1,lst)lst[depth],lst[i] = lst[i],lst[depth]

迭代实现，可以参考完全ｎ叉树，这个应该是一个通用的迭代的处理方法，在这里：只要不在同一列就行了

def perm_backtracking_iteration(depth,lst):size = len(lst)Selected =[-1]*size# 排列数，列号不能重复def place(k):for i in range(k):if Selected[i] == Selected[k]:return Falsereturn Truewhile depth >=0:Selected[depth] +=1#直到选择一个可行的解while Selected[depth]<size and not place(depth):Selected[depth] +=1#这个就是回溯条件，子集树不为空if Selected[depth] <= size-1:if depth == size-1:#print Selected#解码结果，Selected里面对应的是选择了哪一个数for i in Selected:print lst[i],print ""else:#到达下一层时，初始化下一层的子树的范围depth +=1Selected[depth] =-1#回溯，还是从上一层的未选的的地方走else:depth -=1A = ['A','B','C','D']perm_backtracking(0,A)['A', 'B', 'C', 'D']['A', 'B', 'D', 'C']['A', 'C', 'B', 'D']['A', 'C', 'D', 'B']['A', 'D', 'C', 'B']['A', 'D', 'B', 'C']['B', 'A', 'C', 'D']['B', 'A', 'D', 'C']['B', 'C', 'A', 'D']['B', 'C', 'D', 'A']['B', 'D', 'C', 'A']['B', 'D', 'A', 'C']['C', 'B', 'A', 'D']['C', 'B', 'D', 'A']['C', 'A', 'B', 'D']['C', 'A', 'D', 'B']['C', 'D', 'A', 'B']['C', 'D', 'B', 'A']['D', 'B', 'C', 'A']['D', 'B', 'A', 'C']['D', 'C', 'B', 'A']['D', 'C', 'A', 'B']['D', 'A', 'C', 'B']['D', 'A', 'B', 'C']

还可以基于排列树的迭代方式：

def perm_backtracking_iteration2(depth,lst):size = len(lst)Selected =[i for i in range(size)]change = [-1]*size count = 0while depth >=0:# range(Selected[depth],size)记录的是剩余的次数，这里面还不能表现到底是那几次？估计还可以改进if Selected[depth] < size:for i in range(Selected[depth],size):# 交换且记录交换lst[depth],lst[i] = lst[i],lst[depth]change[depth] = iSelected[depth] +=1if depth == size-1:count +=1print lstprint countelse:depth +=1Selected[depth] = depthbreakelse:# 子集树为空了，回溯到上一层,在最底部是没有交换动作的，因为change[depth]就是本身，# 所以需要先-1，再交换，可以自己先调试一遍depth -=1 lst[depth],lst[change[depth]] = lst[change[depth]],lst[depth]change[depth] = -1A = ['A','B','C','D']#perm_backtracking(0,A)perm_backtracking_iteration2(0,A)['A', 'B', 'C', 'D']1['A', 'B', 'D', 'C']2['A', 'C', 'B', 'D']3['A', 'C', 'D', 'B']4['A', 'D', 'C', 'B']5['A', 'D', 'B', 'C']6['B', 'A', 'C', 'D']7['B', 'A', 'D', 'C']8['B', 'C', 'A', 'D']9['B', 'C', 'D', 'A']10['B', 'D', 'C', 'A']11['B', 'D', 'A', 'C']12['C', 'B', 'A', 'D']13['C', 'B', 'D', 'A']14['C', 'A', 'B', 'D']15['C', 'A', 'D', 'B']16['C', 'D', 'A', 'B']17['C', 'D', 'B', 'A']18['D', 'B', 'C', 'A']19['D', 'B', 'A', 'C']20['D', 'C', 'B', 'A']21['D', 'C', 'A', 'B']22['D', 'A', 'C', 'B']23['D', 'A', 'B', 'C']24

如果觉得《回溯法：全排列》对你有帮助，请点赞、收藏，并留下你的观点哦！