标题:
标签:
详情:	输入一个自然数N（1<=N<=9），从小到大输出用1~N组成的所有排列，也就说全排列。例如输入3则输出 123 132 213 231 312 321
输入格式:	输入一个自然数N（1<=N<=9）
输出格式:	N的全排列，每行一个
限制:	每个测试点1秒
样例:	输入 2 输出 12 21 输入 3 输出 123 132 213 231 312 321

方法一：

我们用搜索来实现全排列。DFS就是先按照一条路径去放数字，只到不能再放为止。

假设现在有n个位置，我们来放n个数到n个位置上，每个位置只能放一个数，假设现在我有1,2,3。每次我走到一个位置时我都先放置最小的数，到第n个数字时，我们现在放好了1,2,3，此时并没有结束，下面就要3这个数字，看看前一个位置是否能在产生新的全排列，再收回2,2此时不能在放了，但是可以放3，下面就重复次过程了，知道每个位置都已经放过1,2,3为止。那么我们如何知道在一个位置上还能在放那个数字呢。用一个数组来标记某个数字有没有被使用。

AC代码：

#include 
    
     using namespace std;int n,flag[10],a[10];void dfs(int s)//s：此时所在的位置{	if(s==n+1)	{		for(int i=1;i<=n;i++)			printf("%d",a[i]);		printf("\n");	}	for(int i=1;i<=n;i++)	{		if(flag[i]==0)		{			a[s]=i;//如果没有放置这个数字，那么就放			flag[i]=1;//该数字已经被使用			dfs(s+1);			flag[i]=0;//收回已经使用的数字		}	}	return;}int main(){	scanf("%d",&n);	dfs(1);	return 0;}
    

方法二：

不以此题为例，我们来说说求全排列的第二种方法。例如1,2,3，求全排列时：

先把1固定，然后求{2,3}的全排列，再把2固定，对3求全排列。

那么就有1,2,3

1,3,2。

如果想要求下面的全排列就是让1和后面所有的数字交换一下，再去求全排列。

代码示例：

#include 
    
     using namespace std;int n,a[10];void permutations(int k){	if(k==n)//到达最后一个数字时直接输出即可	{		for(int i=1;i<=n;i++)			printf("%d",a[i]);		printf("\n"); 	}	else	{		for(int i=k;i<=n;i++)//实现交换和之后的全排列 		{			swap(a[i],a[k]); //依次交换两个数			permutations(k+1);//剩下的数进行全排列			swap(a[i],a[k]);//一定要将这一次的交换换回来才能进行下一次的交换		}			} 		}int main(){	scanf("%d",&n);	for(int i=1;i<=n;i++)		a[i]=i;	permutations(1);	return 0;}
    

方法三：

STL中的next_permutation();用法可自行百度。

代码示例：

#include 
    
     #include 
     
      using namespace std;int a[10];int main(){	int n;	scanf("%d",&n);	for(int i=1;i<=n;i++)		a[i]=i;	for(int i=1;i<=n;i++)	{		for(int i=1;i<=n;i++)//此处只打印出前n个排列 			printf("%d",a[i]);		printf("\n");		next_permutation(a+1,a+n+1);	}	return 0;}