全排列--小结

从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。

如1,2,3三个元素的全排列为：

1,2,3

1,3,2

2,1,3

2,3,1

3,1,2

3,2,1

共3*2*1=6种 3！

方法一：

递归法

 1 //代码---递归 
 2 #include<stdio.h>  
 3 #include<string.h>  
 4 const int MAX=11;  
 5 int deep,count;  
 6 int a[MAX];  
 7 bool visit[MAX];  
 8 void dfs(int count){  
 9     if(count==deep) {                          //满足深度时输出  
10         for(int i=0;i<deep;i++)  {  
11             printf("%d",a[i]);  
12         }  
13         printf("
");  
14         return ;                           //返回到上一次的for循环中去  
15     }  
16     for(int i=1;i<=deep;i++){  
17         if(visit[i]){                    //如果i没有被用过  
18             a[count]=i;                //存入数组，待会儿输出  
19             visit[i]=false;            //用过后标记为用过  
20             dfs(count+1);              //继续找下一位数  
21             visit[i]=true;             //函数返回后就意味着回到上一次的for循那么这次的 i定将被释放（不用），那么标记为没用过  
22         }  
23     }  
24 }  
25 int main()  
26 {  
27     int i,j,t,m;  
28     scanf("%d",&t);  
29     while(t--){  
30         scanf("%d",&deep);  
31         memset(visit,true,sizeof(visit));  
32         dfs(0);  
33     }  
34     return 0;  
35 }

方法二：

STL

 1 //代码---STL
 2 #include<iostream>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     int T,i,n;
 9     int a[9]={1,2,3,4,5,6,7,8,9};
10     cin>>T;
11     while(T--)
12     {
13         cin>>n;
14         do
15         {
16             for(i=0;i<n;++i)
17                 cout<<a[i];
18             cout<<endl;
19         }while(next_permutation(a,a+n));
20     }
21     return 0;
22 }

方法三：

 1 //算法书上的感觉还行 
 2 #include <stdio.h>
 3 void f(int n,int *A,int cur)
 4 {
 5     int i,j;
 6     if(cur==n)      //递归边界 
 7     {
 8         for(i=0;i<n;i++)
 9         printf("%d ",A[i]);
10         printf("
");
11     }
12     else
13     {
14         for(i=1;i<=n;i++)   //尝试在 A[cur]中填各种整数 i 
15         {
16             int ok=1;
17             for(j=0;j<cur;j++)
18                 if(A[j]==i) ok=0; //如果 i 已经在 A[0]--A[CUR-1]中出现过，则不能再选 
19             if(ok)
20             {
21                 A[cur]=i;
22                 f(n,A,cur+1);   //递归调用 
23             }            
24         }
25     }
26 }
27 int main()
28 {
29     int n;
30     while(scanf("%d",&n)!=EOF)
31     {
32         int A[20];
33         f(n,A,0);
34     }
35     return 0;
36 }