【算法系列学习一】全排列的生成算法

上节算法课提到了全排列的生成问题，今天自己在网上查找了一些资料，总结起来有一下几种方法：

一.递归类算法。

二.字典序法。

三.递增进位数制法。

四.递减进位数制法。

五.邻位交换法。

六.n进位制法。

下面一一介绍一下这几种算法。

一.递归类算法。

递归类算法比较简洁，实现的方法也有多种。

1.递归算法（非字典序）

 1 #include<iostream>
 2 #include<algorithm>
 3 
 4 
 5 using namespace std;
 6 int sum=0;
 7 int a[10];
 8 int n;
 9 //考虑[l,n-1]区间的全排列 
10 void Perm(int l)
11 { 
12     //输出结果，总排列数加一 
13     if(l==n-1)
14     {
15         for(int i=0;i<n;i++)
16         {
17             printf("%d ",a[i]);
18         }
19         printf("
");
20         sum++;
21      } 
22      else
23      {
24          //考虑[l+1,n-1]的排列 
25          Perm(l+1);
26          for(int i=l+1;i<n;i++)
27          {
28              //当前位(l)与后面的每一位(l+i)分别交换。 
29              swap(a[l],a[i]);
30              //当前位(l)已经确定了 ,现在考虑[l+1,n-1]的排列。 
31              Perm(l+1);
32              //还原 
33              swap(a[l],a[i]);
34          }
35      }
36 }
37 int main()
38 {
39     freopen("data.out","w",stdout);
40     scanf("%d",&n);
41     for(int i=0;i<n;i++)
42     {
43         a[i]=i+1;
44     }
45     Perm(0);
46     printf("共%d种排列。
",sum);
47     return 0;
48 }

View Code

2.回溯法。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<string>
 5 #include<cstring>
 6 using namespace std;
 7 const int maxn=1e2;
 8 int n;
 9 int a[maxn];
10 int b[maxn];
11 int vis[maxn];
12 int sum=0;
13 void dfs(int cur)
14 {
15     if(cur==n)
16     {
17         for(int i=0;i<n;i++)
18         {
19             printf("%d ",b[i]);
20         }
21         printf("
");
22         sum++;
23     }
24     else
25     {
26         for(int i=0;i<n;i++)
27         {
28             if(!vis[i])
29             {
30                 b[cur]=a[i];
31                 vis[i]=1;
32                 dfs(cur+1);
33                 vis[i]=0;
34             }
35         }
36     }
37     
38 }
39 int main()
40 {
41     memset(vis,0,sizeof(vis));
42     scanf("%d",&n);
43     for(int i=0;i<n;i++)
44     {
45         a[i]=i+1;
46     }
47     dfs(0);
48     printf("共%d种
",sum);
49     return 0;
50 }

View Code

二.字典序法。

 1 #include<iostream>
 2 #include<algorithm>
 3 
 4 using namespace std;
 5 int n;
 6 const int maxn=1e2+10;
 7 int a[maxn]; 
 8 const int INF=0x3f3f3f;
 9 bool next_perm()
10 {
11     int k=-1;
12 //    for(int i=0;i<n-1;i++)
13 //    {
14 //        if(a[i]<a[i+1])
15 //        {
16 //            k=i;
17 //        }
18 //    }
19     //从右往左找到满足a[i]<a[i+1]的最靠右的i,排列从这个位置开始改变 
20     for(int i=n-2;i>=0;i--)
21     {
22         if(a[i]<a[i+1])
23         {
24             k=i;
25             break;
26         }
27     }
28     //说明这已经是字典序最大的排列 
29     if(k==-1)
30     {
31         return false;    
32     }
33     //接下来找到在[k+1,n-1]内比a[k]大的最小值，这样才满足是该排列后字典序最小的排列 
34     int ans=INF;
35     int index=0;
36     for(int i=k+1;i<n;i++)
37     {
38         if(a[i]>a[k])
39         {
40             if(a[i]<ans)
41             {
42                 index=i;
43                 ans=a[i];    
44             }
45         }
46     }
47     swap(a[k],a[index]);
48     //接下来把[k+1,n-1]的数倒排 
49     int i=1;
50     while(1)
51     {
52         if(k+i>=n-i)
53         {
54             break;
55         }
56         swap(a[k+i],a[n-i]);
57         i++;
58     }
59     return true; 
60 }
61 int main()
62 {
63     scanf("%d",&n);
64     for(int i=0;i<n;i++)
65     {
66         scanf("%d",&a[i]);
67     }
68     next_perm();
69     for(int i=0;i<n;i++)
70     {
71         printf("%d ",a[i]); 
72     }
73     printf("
");
74     return 0;
75  }

View Code