写在前面：大家好K。首先为你点进这篇有趣的文章👍！文章在撰写过程中难免有疏漏和错误，欢迎你在下方留言指出文章的不足之处；如果觉得这篇文章对你有用，也欢迎你和留下你的评论。更多内容请点进👉我的博客K。👈阅览。

问题：求1、2、3三个数的全排列

1. 分析递归问题

老师：同学们好。今天我们来学习一道全排列的例题，首先请问同学们，递归函数有那两个部分？

同学：老师好。递归函数包含 递归出口和递归体。

老师：没错，那么全排列问题的递归出口是什么？

同学：递归出口是最简单的情况，不用计算过程，计算机能秒出答案。全排列中最简单的情况，就是分解成只有“1个数”的情况：比如，“1”的全排列就是“1”，“2”的全排列就是“3”……

老师：说得对。但是把一个大规模问题的递归过程全展开来学习代码，是十分复杂的，通常我们只选择最简单的过程来分析（当然，只有一个数的过程是最简单的过程，但是这是能直接出答案的过程，对分析问题来说没有意义，这里语境中已经排除掉递归出口的情形），那么，全排列问题中，最简单的过程是什么呢？

同学：最简单的过程是只有两个数的过程，比如只有两个数1、2，我们很容易想出来答案是12和21。通过简单例子来学习递归代码，递归层数不会很深，会更有助于理解代码。老师，您先用两个数的例子来给我们讲解吧。

老师：好。这位同学对于递归的基础已经掌握得很好了，那现在我们通过这道例题来学习一下，看起来很复杂的递归代码，该如何来理解。学会后，对以后学习快速排序、合并排序、动态规划等经常用到递归来解决的问题会很有帮助。现在，我们开始讲解吧！

2. 通过分析两个数的简单情况写代码

老师：我们现在假设有2个数：1、2，它俩的全排列经历了三步，你们来说一说过程呢？

同学：有下面三个步骤：

---------------------------------------------------------------- |①步，对程序来说，原先的大数组有俩元素：1、2；                        | |②步，第一次交换结果仅仅是恰好与初始状态相同，但也是交换了的。           | |③步，拆分成两个小数组：只有一个元素“1”的子数组，只有一个元素“2”的子数组；| ----------------------------------------------------------------  1) 求第一个结果       |       2) 求第二个结果  ①初始俩数：12；      |       ①初始俩数：12；  ②交换顺序：12；      |       ②交换顺序：21；  ③拆分得：1、2；      |        ③拆分得：2、1；  ④组合输出结果：12；   |        ④组合输出结果：21； 

老师：没错，不管有多少个数，都有三个大步骤：拆分大数组—-交换顺序—-组合输出结果。那么来试一下写出俩数全排列的代码吧。

同学：老师，我发现组合输出结果的过程，是最简单的。我们先写这部分代码：

// 数组名为list // 首下标是k，尾下标是m // 当首下标就是尾下标时，说明这是只有一个数的数组 // 换句话说，原大数组已经被拆分到最小（②③步），可以直接输出结果了 if (k==m) { // 循环输出结果 for (int i = 0; i <= m; i++) {       cout << list[i] << " "; }     cout << endl; } 

老师：没错，这是1个数时，即最简单的情况下要做的事情，这也是递归函数的出口。

同学：老师，交换两数的代码可以这样写，对吗？

swap(list[k], list[m]); 

老师：这个代码在只有两个数时是没问题的，但是如果数多了以后，比如，给一组数：1、2、3。k是首下标，m是尾下标。如果仅仅交换这一头一尾的值，交换是不彻底的，永远是123、321，“2”没有做过第一位。所以要通过引入第三个变量，来使数组中所有数都做过第一位。

同学：老师，我们可以通过for循环的控制变量i，来遍历所有情况：

// k永远都是数组的第一个下标，以后拆分成小数组后，k是各小数组的第一位 // i值从k开始，直到和m相等，意味着所有数都做过第一位 for (int i = k; i <= m; i++) { swap(list[k], list[i]); } 

老师：这就对了！现在我们已经把交换顺序和组合输出结果的代码都写出来了：

void perm(int list[], int k, int m) { // 组合输出结果 if (k == m) { for (int i = 0; i <= m; i++) {    cout << list[i] << " "; }   cout << endl; } // 交换顺序 else { for (int i = k; i <= m; i++) { swap(list[k], list[i]); } } } 

那么拆分的代码怎么写呢？

同学：将大数组拆分成小数组，是重复的过程，并且每次范围都要变小（递归，代码如下）。其实变量i值从k开始循环的过程，就已经隐含了拆分的步骤。小数组从大数组中来，编程中实际一直是用一个数组来存储原数组，但是人为通过k值的变化（递归函数调用时k+1），将大数组拆分成想象的小数组。因此循环并不是每次都从原数组的首下标开始。每次循环的首下标都是新的小数组的首下标（即是从i=k开始而不是0开始）。

void perm(int list[], int k, int m) { // 组合输出结果 if (k == m) { for (int i = 0; i <= m; i++) {    cout << list[i] << " "; }   cout << endl; } // 交换顺序 else { for (int i = k; i <= m; i++) { swap(list[k], list[i]); // 这里是递归，函数自己调用自己 // 每次调用该函数时，list(数组名)、m(尾下标)俩值不变 // k值每次都往m靠拢1位，到最后k会与m相等，到达递归出口 perm(list, k + 1, m); } } } 

3. 消灭多个数的“特殊”情况

老师：做到这一步已经很棒了。但是运行一下会发现，只有两个数的时候结果是正确，到三个数以上就不行了。这是哪儿出问题了呢？我们看一下同学们以两个数为例描述的步骤：

1) 求第一个结果        |       2) 求第二个结果  ①初始俩数：12；      |       ①初始俩数：12；  ②交换顺序：12；      |       ②交换顺序：21；  ③拆分得：1、2；      |        ③拆分得：2、1；  ④组合输出结果：12；   |        ④组合输出结果：21； 

我们可以看到，1)的初始数是12，2)的初始数也是12，说明每次开始处理的初始状态是相同的，但是为啥两个数的时候运行正确呢？原因是，2个数的情况太简洁了，没有体现出这种错误。1)的②步交换顺序的结果，恰好是与初始状态相同的，当2)又用到原数组时，自然拿到的数组的顺序貌似就没有变过。

老师：如果是123三个数的话（如下图描述），1)大步①②交换顺序时，同样与初始状态相同的，这一步正确✅，③步拆分得到1和23，还没完，23还需要拆分，然后23被拆分再组合成23和32（就是俩数全排列的情形）✅，即1)大步执行结果就是123、132。但是我们发现了，原数组123经过这几个交换组合后，变成了132。再拿去给2)大步执行，就错了

1) 分而治之 ①初始仨数：123； ②交换顺序：123； ③拆分得：1、23； ④“1”已最简，“23”需再拆分 ****************************** *注：对计算机来说，到这里数组是123* ****************************** 2) 求第一个结果           |       3) 求第二个结果  ①初始俩数：23；         |       ①初始俩数：23；  ②交换顺序：23；         |       ②交换顺序：32；  ③拆分得：2、3；         |       ③拆分得：3、2；  ④组合输出结果：123；     |       ④组合输出结果：132； ****************************** *注：对计算机来说，到这里数组是123* ******************************                                 ******************************                                 *注：对计算机来说，到这里数组是132*                                 ****************************** 

同学：老师，我明白了，3)大步之后，如果再不对数组顺序进行恢复，之后的结果就会出错。事实上，1)2)大步也是需要对数组恢复原顺序的，只是刚好交换完成的顺序与初始状态相同，侥幸逃过了错误。所以我们应该加一行代码，让顺序再换回来：

void perm(int list[], int k, int m) { // 组合输出结果 if (k == m) { for (int i = 0; i <= m; i++) {    cout << list[i] << " "; }   cout << endl; } // 交换顺序 else { for (int i = k; i <= m; i++) { swap(list[k], list[i]); perm(list, k + 1, m); // 上面交换后这里再交换，顺序恢复如初 swap(list[k], list[i]); } } } 

老师：没错，同学们真聪明！

4. 完整代码

同学：这就是我们的全部代码：

#include <iostream> using namespace std; void swap(int &a, int &b) { int tmp = a;   a = b;   b = tmp; } void perm(int list[], int k, int m) { if (k == m) { for (int i = 0; i <= m; i++) {       cout << list[i] << " "; }     cout << endl; } else { for (int i = k; i <= m; i++) { swap(list[k], list[i]); perm(list, k + 1, m); swap(list[k], list[i]); } } } int main() { int list[] = {1, 2, 3, 4}; perm(list, 0, 3); return 0; } 

代码运行结果：