算法基础：全排列问题

全排列是常见的一种场景，对于缺乏更好技巧的时候，作为暴力破解的思路，结合深度遍历使用对初入门者非常有效，代价就是时间复杂度很高。这篇文章介绍一下使用临位对换法来解决全排列的思路和方法。

全排列

• 排列：从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。
• 全排列：当m=n时所有的排列叫全排列。

• 公式：全排列数f(n)=n! (0的全排列0!为1)

常见解法

通常存在如下几种方法解决此此类问题，本文示例主要使用临位对换法进行模拟的实现。

• 字典序法
• 递增进位制数法
• 递减进位制数法
• 邻位对换法

限制与说明

本系列基础文章基本使用c/c++进行，都会使用最为基础的方式进行模拟，只关注与算法最为核心的部分，对于输入输出的各种工程级别的校验，一般不在考虑之列，因为不希望因此让核心代码变得更加冗长，但项目中实际使用的时候要特别留意这些方面。

函数定义与理解

void permutaion(int* list, int k, int n)

• list：待排列的数组
• n：全排列的总的元素数目
• k：在数组下标从0开始的前提下，k表示list中的前k个元素（下标为0～k-1）作为前缀不变化的情况下，对于此问题进行的分解，剩余的k～n进行全排列，所以当k为0的时候，表示为list中元素的全排列n!

实现模拟

void swap(int* x, int* y) { int tmp = *x; *x = *y; *y = tmp; } void permutation(int *list, int k, int n) { if (k == n-1) { for (int i=0; i<n; i++) printf("%d ",list[i]); printf("\n"); return; } for (int i=k; i<n; i++) { swap(&list[k],&list[i]); permutation(list,k+1,n); swap(&list[k],&list[i]); } } 

可以看到实现的要点大概只有寥寥几行，主要说明如下：

• 深度遍历：递归调用的时候事前交换，事后恢复
• 递归调用的时候，k递增，因为全排列初始值为0，自然会增至出口条件n
• 整个长度为n的时候（此处下标为0所以代码为n-1），为递归的出口
• 循环的初值为k而不是0，因为0～k-1的前缀已定

调用示例

int main() { int n = 0; while (scanf("%d",&n) != EOF) { int list[n]; for (int i=0; i<n; i++) { scanf("%d",&list[i]); } permutation(list, 0, n); } } 

注意：可以看到此处使用了list[n]，此种用法是上个实际的C规范C99中提出的，可以使用变量进行定义数组长度，但是需要注意编译器是否支持，而且使用起来可能会有很多问题，只是简单的模拟中又可能都会用到，慎。执行结果示例如下所示：

/Users/liumiao/CLionProjects/untitled/cmake-build-debug/untitled
3
1 2 3
1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 2 1 
3 1 2 
3
3 2 1
3 2 1 
3 1 2 
2 3 1 
2 1 3 
1 2 3 
1 3 2