算法——全排列

一、使用递归算法求全排列（暴力法）
求 {1 2 3 4 5......n}的全排列的思路如下：

（1）让第一个数不同，得到n个数列(办法是：把第1个和后面每个数交换即可)：

1 2 3 4 5......n

2 1 3 4 5......n

.....

n 2 3 4 5......1

以上n个数列，只要第一个数不同，不管后面n-1个数是怎么排列的，这n个数列都不同。

这是递归的第一层

（2）继续：在上面的每个数列中，去掉第一个数，对后面的n-1个数进行类似的排列。例如从上面第2行的{2 1 3 4 5......n}进入第二层(去掉首位2)：

1 3 4 5......n

3 1 4 5......n

......

n 3 4 5......1

以上n-1个数列，只要第一个数不同，不管后面n-2个数是怎么排列的，这n-1个数列都不同。

这是递归的第二层。

（3）继续以上过程，直到用完所有数字。

而我们不难得出，这个算法总共有n×(n-1)×(n-2)×......×1个情况。

代码显示

 1 def swap(s,i,j):     # 实现数组里i，j 互换位置
 2     temp = s[i]
 3     s[i] = s[j]
 4     s[j] = temp
 5 #全排列实现
 6 def perm(begin,end):
 7     global num
 8     if begin == end:
 9         print(nums)
10     else:
11         for i in range(begin,end+1):
12             swap(nums,begin,i)
13             perm(begin+1,end)
14             swap(nums,begin,i)
15 num = 0
16 nums = [1,2,3,4,5,6,7,8,9,10]
17 perm(0,9)

如果想要计算次数，则只需将每一个排列结束时的print语句改成num+=1即可

求n个数中随机m个数的全排列

例如在10个数中取任意3个数的全排列，在递归程序中只修改一个地方就可以了：

1 if begin == 3:         #将end改为3即可
2     print(nums[:3])