python小练习（066）：回溯法（深度优先搜索）实现全排列

mxs_laser

学习学习学习

qaz123765

看下

tang888

赞

luoweiyi

学习学习！

baronyuan

怎么

对门刘大爷

学习

java2python

学习

bujust_h

学习

java2python

看到一个八皇后的算法，其实全排列就是不检查斜线，这个八皇后（或者说八个车）的解，就是全排列
另外八皇后中需要检查皇后位置，这里只要把列表转成词典，检查一下长度就行了（有重复元素，比如到第二层，应该是1，2，如果是1,1，那么词典长度就只有1了，需要排除）：

1. def permutation(n,floor,per):
   
2.     for pos in range(n):
   
3.         if len(set(per + [pos])) == floor:
   
4.             if floor == n:
   
5.                     yield [pos,]
   
6.             else:
   
7.                     for result in permutation(n,floor+1, per + [pos,]):
   
8.                             yield [pos,] + result
   
9. 
   
10. for res in permutation(4,1,[]):
    
11.     print(res)

复制代码

结果：
[0, 1, 2]
[0, 2, 1]
[1, 0, 2]
[1, 2, 0]
[2, 0, 1]
[2, 1, 0]

15538100167

谢谢