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

---

文章目录

全排列常见解法限制与说明函数定义与理解实现模拟调用示例

---

全排列

排列：从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 淼叔 认证博客专家 神经网络 TensorFlow NLP 资深架构师，PMP、OCP、CSM、HPE University讲师，EXIN DevOps Professional与DevOps Master认证讲师，曾担任HPE GD China DevOps & Agile Leader，帮助企业级客户提供DevOps咨询培训以及实施指导。熟悉通信和金融领域，有超过十年金融外汇行业的架构设计、开发、维护经验，在十几年的IT从业生涯中拥有了软件开发设计领域接近全生命周期的经验和知识积累，著有企业级DevOps技术与工具实战。