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

文章目录

• 1. 分析递归问题
• 2. 通过分析两个数的简单情况写代码
• 3. 消灭多个数的“特殊”情况
• 4. 完整代码

问题：求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;
}

代码运行结果：