全排列套路总结

做了2016年的蓝桥杯省赛之后，对于全排列的理解进一步加深，这里做一个小小的总结。

全排列主要有三种方式实现：

库函数：next_permutations(C++)和permutations （python）
递归交换法
递归抽取法

下面一一介绍。

1. 库函数 permutations

由于目前常用python，因此这里只介绍permutations。

这个函数是python内建库itertools的函数（最近发现了两个宝藏python库，可能会单独写一下），用法也比较简单。

permutations('ABCD', 2) # AB AC AD BA BC BD CA CB CD DA DB DC

第一个参数是要排列的数据，第二个参数是选取的个数即：permutations(x, y) -> $A_x^y$。如果省略y参数，默认为全排列（$A_n^n$）。

需要注意的是：

排列依字典序发出。因此，如果 x 是已排序的，排列元组将有序地产出。
即使元素的值相同，不同位置的元素也被认为是不同的。如果元素值都不同，每个排列中的元素值不会重复。即 permutations('000', 3) 输出为[('0', '0', '0'), ('0', '0', '0'), ('0', '0', '0'), ('0', '0', '0'), ('0', '0', '0'), ('0', '0', '0')]。

既然谈到了permutation，那就顺便说一下同一个库中的combination。

combinations('ABCD', 2) --> AB AC AD BC BD CD

参数用法同上，即combinations(x, y) -> $C_x^y$。

注意事项：

组合按照字典序返回。所以如果输入 x是有序的，生成的组合元组也是有序的。
即使元素的值相同，不同位置的元素也被认为是不同的。如果元素各自不同，那么每个组合中没有重复元素。

2. 递归交换法

这个方法其实就是dfs的回溯算法，直接在原序列进行交换和枚举。代码框架如下：

a = [1, 2, 3, 4, 5, 6] # 原数据
n = len(a) # 总长度
ans = 0 # 符合条件的排列个数 即求解的答案
def f(k): # 递归
    global ans 
    if k == n: # 排列完全
        if check(): # 如果满足条件则计数 check根据情况自定义
            ans += 1
        return

    for i in range(k, n): # 开始从k位置进行交换枚举
        swap(a, i, k)
        # 可以在此提前剪枝，符合条件再继续递归。
        f(k+1) # 递归
        swap(a, i, K) # 回溯

这个方法生成的就是序列a的全排列，是将a中的每个元素当作不同的独立的元素来做的。如果数量稍微大一些可能会时间较长，可以在递归前提前剪枝。

3. 递归抓取法

这个方法也是利用回溯的思想，不同的是需要用一个额外的path参数来记录当前抓取到的选择。这种抓取的思路就是按顺序从原序列中进行选择，全部选择完后即为答案。可以通过增加判断去除重复的情况，原理是确定一个固定的抓取顺序，这样所有的情况就是唯一的了。举例来说，就是如果a[1]=0, a[2]=0，则我先选择a[1]再选择a[2]和先选择a[2]再选择a[1]是同一种情况（数量更多出现的重复次数更多）。这时候，我们只需要规定一个固定的顺序，排除其他情况，就可以避免重复的出现。即规定必须先选择a[1]后才能选择a[2]，这样即使元素相同但是每种情况也都是唯一的了。

a = [0, 0, 0, 0, 0, 0, 1, 1 ,1 ,1] # 原序列
n = len(a)
vis = [False] * n # 标记哪些元素被抓取过
ans = 0

def f(pos, path): # pos为当前枚举到的path位置 path记录当前的选择
    global ans
    # 此部分同上
    if pos == n:
        if check():
            ans += 1
        return

    for i in range(n): # 枚举抓取序列中的每个元素
        #用于排除重复情况 即将不同位置的相同元素示为同一种情况
        # 如果a[i]与a[i-1]相同并且a[i-1]还未被抓取，则这种情况会产生重复，直接跳过
        if i > 0 and a[i] == a[i-1] and not vis[i-1]: 
            continue
        # 如果a[i] 还未被抓取，则可以进行枚举
        if not vis[i]:
            vis[i] = True
            path[pos] = a[i]
            f(pos+1, path)
            vis[i] = False # 回溯