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

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

一.递归类算法。

二.字典序法。

三.递增进位数制法。

四.递减进位数制法。

五.邻位交换法。

六.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("\n");
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种排列。\n",sum);
47     return 0;
48 }

2.回溯法。

二.字典序法。

 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("\n");
74     return 0;
75  } 

时间: 03-16

【算法系列学习一】全排列的生成算法的相关文章

全排列的生成算法

[复制转载] //全排列的生成算法 // 全排列的生成算法就是对于给定的字符集,用有效的方法将所有可能的全排列无重复无遗漏地枚举出来.任何n个字符集的排列都可以与1-n的n个数字的排列一一对应, // 因此在此就以n个数字的排列为例说明排列的生成法. // n个字符的全体排列之间存在一个确定的线性顺序关系.所有的排列中除最后一个排列外,都有一个后继:除第一个排列外,都有一个前驱.每个排列的后继都可以从 // 它的前驱经过最少的变化而得到,全排列的生成算法就是从第一个排列开始逐个生成所有的排列的方

简单探讨全排列的生成算法

在研究组合数学的时候,常常能够碰见要求生成全排列的情况.下面来简单探讨全排列的递归生成算法. 现有一个序列(1,2,3),将其命名为序列S<a1,a2,a3>, 假定A(a1,a2,a3) 为这个序列的全排列,那么我们可以得到如下若干序列: <a1,A(a2,a3)>  ① <a2,A(a1,a3)>  ② <a3,A(a1,a2)>  ③ 我们再来看①,她还可以展开成如下两个序列: <a1,a2,A(a3)>  ⑤ <a1,a3,A(a2

全排列生成算法

全排列的生成算法, next_permutation_1 可以用于生成多重集的全排列,next_permutation_2不能用于多重集 #include <cstdio> #include <cstring> #include <vector> using namespace std; bool next_permutation_1(vector<int>& vec){ int n = vec.size()-1; for(;n>0;n--){

计算机图形学 - 全斜率直线中点生成算法

算法描述: 直线中点生成算法 假定直线斜率k在(0,1]之间,当前像素点为,则下一个像素点有两种可选择点P1或P2. 若P1与 P2的中点称为M,Q为理想直线与x=xp+1垂线的交点. • 当M在Q的下方时,则取P2为下一个像素点: • 当M在Q的上方时,则取P1为下一个像素点. 这就是中点画线法的基本原理. 算术推导: 详细代码:Computer Graphics - code_1 生成结果:

递归解决全排列生成算法

排列:从n个元素中任取m个元素,并按照一定的顺序进行排列,称为排列: 全排列:当n==m时,称为全排列: 比如:集合{ 1,2,3}的全排列为: { 1 2 3} { 1 3 2 } { 2 1 3 } { 2 3 1 } { 3 2 1 } { 3 1 2 } 方法一: 我们可以将这个排列问题画成图形表示,即排列枚举树,比如下图为{1,2,3}的排列枚举树,此树和我们这里介绍的算法完全一致: 算法思路: (1)n个元素的全排列=(n-1个元素的全排列)+(另一个元素作为前缀): (2)出口:如

[LeetCode] Permutations 排列生成算法之字典序法

字典序排序生成算法 字典序法就是按照字典排序的思想逐一产生所有排列. 例如,由1,2,3,4组成的所有排列,从小到大的依次为: 1234, 1243, 1324, 1342, 1423, 1432, 2134, 2143, 2314, 2341, 2413, 2431, 3124, 3142, 3214, 3241, 3412, 3421, 4123, 4132, 4213, 4231, 4312, 4321. 分析这种过程,看后一个排列与前一个排列之间有什么关系? 再如,设有排列(p)=276

算法设计:全排列算法代码实现

在上星期的算法设计课程的学习中,我们学习了两种全排列算法,该算法用于求出数组{1,2,3,...,n}的所有可能的排列,今天我们就来看看这个算法的具体代码实现. 1. 第一种算法 第一种算法和我们现实生活中习惯的方法较为相似,以{1,2,3}为例,我们先写出第一种排列123,然后将2与3交换,得到132:再回到123,交换1与2得到213,再将1与3交换.....直到得到所有的排列. 该算法伪码如下: PERMUTATIONS1(int n): for j←1 to n a[j]←j end f

等高线生成算法(转载)

等高线生成算法 输入:离散的采样点坐标和高度值(x_0,y_0,value_0),(x_1,y_1,value_1)......(x_n, y_n, value_n) 输出:等高线图,如下所示 wiki上的Marching squares算法对此有很好的说明,我也是按照wiki上面的步骤来实现这个算法的,下面对该算法的步骤进行简要说明. 输入参数: 1.点的集合(x_0,y_0,value_0),(x_1,y_1,value_1)......(x_n, y_n, value_n) ; 2.高度值

清华版CG 实验2 直线生成算法实现

1.实验目的: 理解基本图形元素光栅化的基本原理,掌握一种基本图形元素光栅化算法,利用OpenGL实现直线光栅化的DDA算法. 2.实验内容: (1) 根据所给的直线光栅化的示范源程序,在计算机上编译运行,输出正确结果: (2) 指出示范程序采用的算法,以此为基础将其改造为中点线算法或Bresenham算法,写入实验报告: (3) 根据示范代码,将其改造为圆的光栅化算法,写入实验报告: (4) 了解和使用OpenGL的生成直线的命令,来验证程序运行结果. 3.实验原理: 示范代码原理参见教材直线