C语言实现全排列（dfs方法）

####学习记录自用，废话较多，欢迎批评指正

C语言实现全排列

输入：一个数字n

输出：1~n的全排列

例：

输入：

3

输出：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

思路：

        使用dfs深搜。

        1、首先定义全局变量。mark[100]用来标记该位置是否被搜索过，a[10] 用来记录排列结果。n是输入的数字。

#include <stdio.h>
int n,mark[100],a[10];

        2、然后写主函数（没什么技术含量的部分），深搜从step=1开始。

int main()
{
	scanf("%d",&n);
	dfs(1);
	return 0;
}

        3、接下来是深搜的思路。

        其实是一个很基础的dfs应用，但由于本人刚学很不熟悉所以还是详细说一遍（给自己讲一遍）。

        直接讲可能不是很友好，拿n=3为例子进行说吧。

        从主函数进入dfs函数。此时step=1，代表着第一步。（这个step具体的作用在于排列元素的标号，在深搜的过程中，会使用a[step]=i的方式来给以排列列表进行赋值）

        此时mark数组全为0。我们使用循环，从第一个点开始搜索。首先判断mark[i]==0（此时i==1），进入赋值部分，首先标记mark[i]=1,表示第一个点已经被搜索过（也就是此次排列的第一个元素已经确定），然后进行赋值，a[1]=i，第一个元素被赋值1。       

        到此为止第一个元素就已经确定了。此时的非零变量值为：

        a[1]=1;

        mark[1]=1;

        然后对第二个元素进行处理，也就是进行第一个元素下分支的深搜。此时用dfs(step+1)进行下一次深搜。

        第二次深搜仍然通过循环来实现。首先判断首先判断mark[i]==1（此时i==1），故不进入循环，i++，i=2时mark[i]==0，进入循环。同上一样，标记mark[2]=1，赋值a[2]=2，随后进入第三个元素的处理。

        此时的非零变量值为：

        a[1]=1;a[2]=2；

        mark[1]=1;mark[2]=1；

         对于3步骤的处理，是类似的方法。

         此时的非零变量值为：

        a[1]=1;a[2]=2;a[3]=3;

        mark[1]=1;mark[2]=1;mark[3]=1;

        在此分支结束后，我们得到的是“1 2 3”的序列。

        当step=4时，step已经大于n，故不进行排列。对step进行判断，当step> n时，输出排列结果，并返回上一分支。返回上一分支后要对该点的mark标记清零。在此情景中,即mark[3]=0。

        此时的变量值为：

        a[1]=1;a[2]=2;a[3]=3;

        mark[1]=1;mark[2]=1;mark[3]=0;

         此时i=3，i<=n，不再进入循环，于是退出本次dfs函数，回到第二层搜索。此时i=2（是第二层的数据），mark[2]清零，i++。

        此时的变量值为：

        a[1]=1;a[2]=3;a[3]=2;

        mark[1]=1;mark[2]=0;mark[3]=0;

        再次进入判断，mark[i]==0（i==3），于是a[2]=3,mark[3]=1，再次进入下一层搜索，a[3]=2,mark[2]=1。得到排列“1 3 2”。

        同上一样退出循环，此时第二层的i=3，i=n，故退出循环，回到第一层，第一层i=1，i++。

        此时的变量值为：

        a[1]=1;a[2]=3;a[3]=2;

        mark[1]=0;mark[2]=0;mark[3]=0;

        此时i=2，同i=1一样进行深搜，具体流程不多赘述，得到的排列是“2 1 3”和“2 3 1” 。

        退出i=2的搜索之后，i++，i=3，仍然像之前一样进行搜索，得到的排列是“3 1 2”“3 2 1”。

        直到第一个进入的dfs循环结束后，退出函数，结束运行。

        完整代码见下：

/*在学完圆的面积公式之后，我们的数学老师数学兔一时兴起，
决定教学排列组合，在正式教学前呐，数学兔希望小朋友们解决一个全排列问题：
全排列问题就是要把[1,n]里的数都按照字典序排列出来
如，当n=3时，他的全排列如下：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
输入描述
一个整数1<=n<=8​。
输出描述
按照字典序顺序每行输出一个排列，数字之间用空格隔开。*/
#include <stdio.h>
int n,mark[100],a[10];
void dfs(int step)
{
	if(step>n)
	{
		for(int i=1;i<=n;i++)
		{
			printf("%d",a[i]);
			if(i!=n)
			{
				printf(" ");
			}
			else 
				printf("n");
		}
	}
	else
	{
		for(int i=1;i<=n;i++)
		{
			if(mark[i]==0)
			{
				mark[i]=1;
				a[step]=i;
				dfs(step+1);
				mark[i]=0;
				
			}	
		}
		
	}
}
int main()
{
	scanf("%d",&n);
	dfs(1);
	return 0;
}