在写一些概率统计题的模拟时，经常需要把A(n,n)、C(n,m)的排列组合全部列出来，这里记录一下A(n,n)全排列全部遍历的实现。根据概率论中的排列组合知识知道A(n,n)=n!=n*(n-1)…*1；最终结果数是n的阶乘个，例如对于集合{1,2,3},有6种全排列。
要枚举出所有的排列结果，我们从n=1开始来看，集合{1}的全排列就是{1}，n=2时，有 {1,2} 和 {2,1} ，可以看成是2和1交换位置，然后对{1}进行全排列；对{1,2,3}，先2和1交换，得到{2}和{1,3}，对{1,3}采用和n=2的情况相同的处理，所以是可以递归的，于是采用递归来写，递归终止条件可以用n=1，也可以在n=2的时候就交换然后返回，归纳一下是将每个元素放到余下n-1个元素组成的队列最前方，对剩余元素进行递归全排列。用Python翻译这一思路：
def perm(lst): #input:list, 一个字符串格式的元素列表
n=len(lst)
if n<=1:
return lst
elif n==2:
return [lst[0]+lst[1],lst[1]+lst[0]] #终止条件
kk=[]
for i in range(n):
nlst=lst[0:i]+lst[i+1:] #除lst[i]外的元素
c=perm(nlst)
ss=[lst[i]+j for j in c]
kk.extend(ss) #注意是extend不是append
return kk
上面perm函数被递归调用了。输出格式是一个一维的数组。测试：
s=perm(['1','2','3']) #perm(list('123'))
print(s)
#['123', '132', '213', '231', '312', '321']
看一篇文章发现leetcode上正好有一个全排列的题：46. Permutations，不过其输入是一个整数数值列表，输出二维数组：
Given a collection of distinct integers, return all possible permutations.
Example:
Input: [1,2,3]
Output:[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
简单改一下代码：
class Solution(object):
def permute(self, nums):
"""
:type lst: List[int]
:rtype: List[List[int]]
"""
n=len(nums)
if n<=1:
return [nums]
elif n==2:
return [[nums[0],nums[1]],[nums[1],nums[0]]]
kk=[]
for i in range(n):
nlst=nums[0:i]+nums[i+1:]
c=self.permute(nlst)
ss=[]
for j in c:
w=[nums[i]]
w.extend(j)
ss.append(w)
kk.extend(ss)
return kk
通过了测试：
另外发现Python的库itertools有很好用的轮子：permutations和product，列出全排列很方便：
from itertools import permutations
print(list(permutations('1234')))
而且permutations支持两个参数，例如permutations('ABCD', 2)得到AB AC AD BA BC BD CA CB CD DA DB DC，就是从ABCD中任选两个排列，A(4,2)。官方文档给出了permutations(iterable[, r])实现的等价代码，是很好的参考资料。
具体关于permutations和product，可以看官方文档：https://docs.python.org/2/library/itertools.html#itertools.permutations。
