全排列 回溯法_字典序全排列 回溯

全排列可以说是最基本的部分了，不过实现的过程还是很有必要学习的，可以说难者不会，会者不难。

大体思路如下：

第一步：从n个数中选取第一个排列的第一个元素，如1；

第一步：从n个数中选取第一个排列的第二个元素，如2；

......

第n步：从n个数中选取第一个排列的第n个元素，如n；

当然不能选重复的。到此，第一个排列已经选出来了。那么第二个排列怎么选呢，其实很简单。

上一个排列执行到第n步后，这个函数不再执行，进行回溯，那么就会回到第n-1步，这时前面的n-1

个数都已经选过了，所以第n-1步选择的就会是n了，然后第n步选择的就是n-1；

所以第一个排列是：1 2 3 。。。n-1 n；

第二个是：1 2 3 。。。n n-1；

以此类推就会输出所有的排列，代码如下。

#include<iostream>
using namespace std;
int n,a[100],v[100];
//a数组用于保存每一次的排列，v数组用于判断数字是不是已经被选过 
void dfs(int dp)//dp从1到n，执行n次，每次选择一个数 
{
	if(dp>n)//dp为n+1的时候，就说明已经选了n个，可以输出了； 
	{
		for(int i=1;i<=n;i++)
		{
			cout<<a[i]<<" ";
		}
		cout<<endl;
		return;
	}
	for(int i=1;i<=n;i++) 
	{
		if(!v[i])//判断是不是选择过 
		{
			a[dp]=i;//保存当前选择 
			v[i]=1;//标记这个数字，防止同一个排列选择相同的数字。 
			dfs(dp+1);
			v[i]=0;//回溯回来的时候一定要清楚标记，不然下一个排列就能选择了，这也是最关键的地方，仔细思考一下。 
		}
	}
} 
int main()
{
	while(cin>>n)
	{
		dfs(1);
	}
}

运行结果：，很明显，这是字典序。

还有另外一种实现的方法，有着很好的用处，可以方便的解决一些搜索的题目。

答题思路就是我选择了一个元素，那么就把这个元素交换到当前这个位置，就不用开一个数组标记了，直接给代码吧，兄弟们

可以自己用笔和纸走一遍，就会明白了，我认为这种思想很有用处的。

#include<iostream>
using namespace std;
int n,a[100];
void dfs(int dp)
{
	if(dp>n)
	{
		for(int i=1;i<=n;i++)
		{
			cout<<a[i]<<" ";
		}
		cout<<endl;
		return;
	}
	for(int i=dp;i<=n;i++)
	{
		swap(a[i],a[dp]);//交换 
		dfs(dp+1);
		swap(a[i],a[dp]);//回溯回来的时候一定要换回来 
	}
}
int main()
{
	while(cin>>n)
	{
		for(int i=1;i<=n;i++)
		{
			a[i]=i;//初始化a数组， 
		}
		dfs(1);
	}
}

结果：很显然，不是字典序，可以和上一个截图对比一下，有的题目会要求用字典序输出，所以要小心一点。

举一反三的时候到了，兄弟们可以做一下这一道题，完全用的就是上面的方法，如果你能写出来，那么就是真的理解了。

题目：

6

1 4 3 2 5 6
1 6 5 2 3 4

大家先试一下，想要代码的可以评论，然后我会把代码给大家，就按照上面的思想就可以了。

还有，大家觉得讲的好的话，可以支持一下作者，当然也可以提建议，，谢谢兄弟们了。