我们从全排列开始。
打表&枚举
如何得到一个2位数的全排列？
cout<<12<<" "<<21;
2位打表足矣。
4位呢？还打表吗？
for(int i=1;i<=4;i++)
for(int j=1;j<=4;j++)
for(int k=1;k<=4;k++)
for(int o=1;o<=4;o++)
if(i!=j&&i!=k$$i!=o&&j!=k&&j!=o&&o!=k)
cout<<i<<j<<k<<o<<" ";
枚举每一位，当每个数都不同时输出。
深度优先搜索dfs
要生成一个3位数的全排列，我们假设有一个长度为3的数列，依次存放数，当数列满的时候就有了一个新的全排列。
过程如下：
\[()()() \]\[(1)()() \]\[(1)(2)() \]\[(1)(2)(3) \]此时输出
123；\[(1)(2)() \]\[(1)(3)() \]\[(1)(3)(2) \]此时输出
123；\[(2)()() \]\[(2)(1)() \]\[(2)(1)(3) \]此时输出
213；\[(2)(1)() \]\[(2)(3)() \]\[(2)(3)(1) \]此时输出
231；\[(3)()() \]\[(3)(1)() \]\[(3)(1)(2) \]此时输出
312；\[(3)(1)() \]\[(3)(1)() \]\[(3)(1)(2) \]此时输出
312。
思路应该看明白了，每次插入现有的最小的数，数组满了后输出一可行解，然后收回上次插入的数，并寻找新的解。
这就是深度优先搜索，搜索->有序的尝试每一种可能。
（Q：那枚举不也是尝试每一种可能吗？）
（A：其实枚举也是搜索的一种。）
深度优先搜索就是每一种可能尝试到底，类似走迷宫一直靠右边的墙走。
深度优先搜索模板
void dfs(int step) { 判断边界 for(int i=0;i<n;i++) 尝试每一种可能 { dfs(step+1);继续下一步 } 返回 }
#include <iostream>
using namespace std;
int a[10],book[10],n;
void dfs(int step)
{
int i;
if(step==n+1)//已经完成了一组全排列（判断边界）
{
for(i=1;i<=n;i++)//输出
cout<<a[i];
cout<<" ";
return;//返回
}
for(i=1;i<=n;i++)//尝试每一种可能
{
if(book[i]==0)//没有用过这个数
{
a[step]=i;//使用
book[i]=1;//标记用过
dfs(step+1);//尝试下一个数
book[i]=0;//收回
}
}
return;//返回
}
int main()
{
cin>>n;
dfs(1);//从第一位开始尝试
return 0;
}
/*
一组输入输出样例如下：
in:
4
out:
1234 1243 1324 1342 1423 1432 2134 2143 2314 2341 2413 2431 3124 3142 3214 3241 3412 3421 4123 4132 4213 4231 4312 4321
*/
番外——全排列 STL
首先我们要知道C++有一个特别神奇的库algorithm，这个库里面有很多神奇的函数。
其中一个可以很快解决我们这道题的就是next_permutation()。
什么意思呢？就是一个求一个排序的下一个排列的函数，可以遍历全排列。
使用方法——不可开袋及食
next_permutation()用来生成一个序列的全排列，也就是要给他一组数，而不是一个数。
所以先初始化一个数组，使之为：\[a[]={1,2,3,4,5,6,7,8,9}; \]然后使用时
next_permutation(a,a+n)即可生成一组全排列。只有一组？
是的。再次调用即可生成下一组，所以需要知道共有多少组。
全排列组数为\(A^{n}_{n}=n!\)，有兴趣的可以baidu。
//生成4位数全排列
#include <iostream>
using namespace std;
int a[100],t=1;//t为个数
int main()
{
for(int i=1;i<=4;i++)
{
a[i]=i;
t*=i;
}
for(int i=1;i<=t;i++)
{
for(int j=1;j<=n;++j) cout<<a[j]<<" "<<endl;
next_permutation(a+1,a+n+1);//生成下一组
}
return 0;
}