递归求全排列的学习与理解
递归求全排列
作者：CnZBin
全排列：
从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。
输出自然数 1 到n所有不重复的排列，即 n 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。
比如：求1~3的全排列
由中学的知识便知共有 3! =3 x 2 x 1=6种 排列，即123，132，213，231，312，321
那么该怎么用代码求出来呢？像我这种萌新，一开始想到的当然是用for循环，但是求1~3的全排列可以用3个for循环，那么当要求1-n(n为用户输入)，for循环的个数便确定不了了。
于是，便需要用递归了。看了很多大佬的代码都看不太懂，最后还是得自己推一遍才懂，还是得多动手啊！
代码如下：
#include
using namespace std;
int a[20],flag[20]; //a用来装产生的排列 flag为标记数组
//虽然计算机可以算较大的数排列，但是越大时间越长，还会产生栈溢出的情况，这里就只开了20个空间的数组
int n; //n : 产生n个数的全排列
void DFS(int step) //step可以理解为一个排列的第几个数字
{
if(step==n+1) //当step达到要排列的个数时，就输出
{
for(int i=1;i<=n;i++)
printf("%5d",a[i]); //每个数字空5格输出
cout<<endl;
}
for(int i=1;i> n;
DFS(1); //从第一个数字开始
return 0;
}
下面举例求1~4的全排列，函数初始值传入1
以此类推，数组a,flag被赋值为
数组a:
| 下标 | 值 |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
| 4 | 4 |
数组flag:
| 下标 | 值 |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 2 | 1 |
| 3 | 1 |
| 4 | 1 |
当DFS（4）执行到DFS(4+1)即DFS（5）时，进入函数出口，满足if(5=4+1)，DFS(5）退出，开始回溯，图解如下：
每次排列完4个就输出一次。
总而言之，整个过程就是从数组前面往后排列数字，然后不断从后面开始向前面更新。
理解该过程要结合栈的递归，搞清楚各个步骤，尤其是一个函数结束返回上一层以及回溯的过程。而要写出这种递归代码还是需要多做题啊！
作者：CnZBin
相关文章
Tertia
2020-10-26
Iris
2021-08-03
Letitia
2020-11-27
Kande
2023-05-13
Ula
2023-05-13
Jacinda
2023-05-13
Winona
2023-05-13
Fawn
2023-05-13
Echo
2023-05-13
Maha
2023-05-13
Kande
2023-05-15
Viridis
2023-05-17
Pandora
2023-07-07
Tallulah
2023-07-17
Janna
2023-07-20
Ophelia
2023-07-20
Natalia
2023-07-20