生成n个数的全排列【递归、回溯】-阿里云开发者社区

开发者社区> 人工智能> 正文
登录阅读全文

生成n个数的全排列【递归、回溯】

简介: 下面讨论的是n个互不相同的数形成的不同排列的个数。毕竟,假如n个数当中有相同的数,那n!种排列当中肯定会有一些排列是重复的,这样就是一个不一样的问题了。/*===================================== 数的全排列问题。
下面讨论的是n个互不相同的数形成的不同排列的个数。
毕竟,假如n个数当中有相同的数,那n!种排列当中肯定会有一些排列是重复的,这样就是一个不一样的问题了。


/*
===================================== 数的全排列问题。将n个数字1,2,…n的所有排列枚举出来。 2 3 1 2 1 3 3 1 2 3 2 1 思路: 递归函数定义如下: void fun(int a[],int flag[],int i,int ans[]); //原始数据存放于a[]。flag[]的每一个元素标记a[]对应位置处的元素是否已经被选用。 //i表示当前对某排列而言,正在寻找到第i个数据。 //ans[]是存放每一个排列的地方。每当放够n个元素到ans则开始打印该数组。 程序中先把原始数据读入到数组a[]。flag[]数组元素全部置0. 生成一个排列的过程可以这样认为: 每次递归都扫描flag[],寻找一个flag[i]==0然后把a[i]选到排列当中。 (也即放到ans[i]当中。选a[i]后要把flag[i]置1.) 这样就确定了当前排列的第i个元素。 然后递归进入下一层确定第i+1个数。 以此类推,逐层递归直至i==n-1(因为i从0开始,所以是i==n-1)就认为已经得到了一个 完整的排列。这个时候可以把ans数组输出了。 输出后可以开始回溯了。 每次回溯都要把flag[i]置0以便还原现场。(相当于ans[i]不选a[i]了。) 置0后继续循环枚举当前位置的其他可能取值。 ======================================*/

下面是我自己按照自己的理解做的,其实有点浪费空间了:

 1 #include<stdio.h>
 2 int n,count;//n表示参与排列的数据的个数,count表示不同排列的个数 
 3 void fun(int a[],int flag[],int i,int ans[]);
 4 //原始数据存放于a[]。flag[]的每一个元素标记a[]对应位置处的元素是否已经被选用。
 5 //i表示当前对某排列而言,正在寻找到第i个数据。 
 6 //ans[]是存放每一个排列的地方。每当放够n个元素到ans则开始打印该数组。 
 7 int main()
 8 {
 9     int i;
10     int a[20],flag[20],ans[20];
11     freopen("5.out","w",stdout);
12     scanf("%d",&n);
13     for(i=0;i<n;i++)
14     {
15         flag[i]=0;
16         a[i]=i+1;
17     }
18     count=0;
19     fun(a,flag,0,ans);//从第0号开始出发,依次确定每一个位置的数值 
20     printf("total:%d\n",count);
21     return 0;
22 }
23 void fun(int a[],int flag[],int i,int ans[])
24 {
25     int j,k;
26     if(i==n-1) 
27     {
28         for(j=0;j<n;j++)
29         {
30             if(flag[j]==0)//找到了一个排列,把这个排列给输出。
31             {
32                 ans[i]=a[j];
33                 for(k=0;k<n;k++) printf("%d ",ans[k]);
34                 printf("\n");
35                 count++;
36                 return ;
37             } 
38         }
39     }
40     else
41     {
42         for(j=0;j<n;j++)
43         {
44             if(flag[j]==0)
45             {
46                 ans[i]=a[j];
47                 
48                 flag[j]=1;
49                 fun(a,flag,i+1,ans);
50                 flag[j]=0;
51             }
52         }
53     }
54 }
View Code

-----------------------------------------------------插入分割线-----------------------------------------------------

代码OJ测试:http://ica.openjudge.cn/dg3/solution/10102944/

题目要求:原序列是字母,而且字母不重复,而且原序列按字典序升序排列,要求生成的所有排列按字典序升序输出。

AC代码:(把上面的代码做简单修改即可) 

 1 #include<stdio.h>
 2 #include<string.h>
 3 
 4 int n,count;//n表示参与排列的数据的个数,count表示不同排列的个数 
 5 void fun(char a[],int flag[],int i,char ans[]);
 6 //原始数据存放于a[]。flag[]的每一个元素标记a[]对应位置处的元素是否已经被选用。
 7 //i表示当前对某排列而言,正在寻找到第i个数据。 
 8 //ans[]是存放每一个排列的地方。每当放够n个元素到ans则开始打印该数组。 
 9 
10 int main()
11 {
12     int i;
13     int flag[20];
14     char a[20],ans[20];
15     scanf("%s",a);
16     //scanf("%d",&n);
17     n=strlen(a);
18     for(i=0;i<n;i++)
19     {
20         flag[i]=0;
21         //a[i]=i+1;
22     }
23     count=0;
24     fun(a,flag,0,ans);//从第0号开始出发,依次确定每一个位置的数值 
25     //printf("total:%d\n",count);
26     return 0;
27 }
28 void fun(char a[],int flag[],int i,char ans[])
29 {
30     int j,k;
31     if(i==n) 
32     {
33     for(k=0;k<n;k++) printf("%c",ans[k]);
34         printf("\n");
35         count++;
36         return ;
37     }
38     else
39     {
40         for(j=0;j<n;j++)
41         {
42             if(flag[j]==0)
43             {
44                 ans[i]=a[j];
45                 
46                 flag[j]=1;
47                 fun(a,flag,i+1,ans);
48                 flag[j]=0;
49             }
50         }
51     }
52 }
View Code

-----------------------------------------------------分割线结束-----------------------------------------------------

下面是书上的代码,比较好一点,不过一开始可能不好理解。建议看懂了上面的再来看这段代码。

 1 #include<stdio.h>
 2 int n,a[20];
 3 long count=0;
 4 void fun(int k); //fun(k)表示现在正在确定某个排列当中的第k个数 
 5 //也可以认为fun(k)是生成第k个数到第n个数的所有排列。 
 6 int main()
 7 {
 8     int i;
 9     scanf("%d",&n);
10     for(i=0;i<n;i++)
11     {
12         a[i]=i+1;
13     }
14     fun(0);
15     printf("total:%d\n",count);
16     return 0;
17 }
18 void fun(int k)//fun(k)表示现在正在确定某个排列当中的第k个数 
19 {
20     int j,t;
21     if(k==n)
22     {
23         count++;
24         for(j=0;j<n;j++) printf("%d ",a[j]);
25         printf("\n");
26         return ;
27     }
28     else
29     {
30         for(j=k;j<n;j++)//注意:这里是在原始数组内交换数据实现排列,所以j从k开始 
31         {
32             t=a[k];a[k]=a[j];a[j]=t;
33             fun(k+1);
34             t=a[k];a[k]=a[j];a[j]=t;
35         }
36     }
37 }
View Code

下面是网上对这个问题的代码,也不错。

 1 #include <stdio.h>
 2 
 3 void print(int array[], int end);
 4 void swap(int &a, int &b);
 5 void permute(int array[], int begin, int end);
 6 
 7 void permute(int array[], int begin, int end)
 8 {
 9     if (begin == end)
10     {
11         print(array, end);
12     }
13     else
14     {
15         for (int j = begin; j <= end; ++j)
16         {
17             swap(array[j], array[begin]);
18             permute(array, begin+1, end); //recursive,enlarge problem's scope
19             swap(array[j], array[begin]); //backtracking
20         }
21     }
22     return;
23 }
24 
25 void print(int array[], int end)
26 {
27     for (int i = 0; i <= end; ++i)
28     {
29         fprintf(stdout, "%d", array[i]);
30         if (i != end)
31         {
32             fprintf(stdout, "\t");
33         }
34     }
35     fprintf(stdout, "\n");
36     return;
37 }
38 
39 void swap(int &a, int &b)
40 {
41     int temp = a;
42     a = b;
43     b = temp;
44     return;
45 }
46 
47 int main()
48 {
49     int array[]={1,2,3,4};
50     permute(array,0,3);
51     return 0;
52 }
View Code

 

/*==============================================================================
下面的分析来自王晓东编著的《算法设计与分析(第2版)》,清华大学出版社出版 ,
第2章递归与分治策略例题2.4排列问题。
设R={r1,r2,r3,...,rn}是要进行排列的n个元素,Ri=R-{ri}。 集合X中的元素的全排列记为perm(X)。(ri)perm(X)表示在全排列perm(X)的每一个 排列前加上前缀ri得到的排列。R的全排列可归纳定义如下: 当n=1时,perm(R)=(r),其中r是集合R中唯一的一个元素。 当n>1时,perm(R)由(r1)perm(R1),(r2)perm(R2),...... ,(rn)perm(Rn)构成。 依此递归定义,可以设计产生perm(R)的递归算法如下: (详见下面代码) ================================================================================
*/
public static void perm(Object[] List,int k,int m)
{//产生list[k:m]的所有排列
    if(k==m)
    {//只剩一个元素
        for(int i=0;i<=m;i++)
            System.out.print(List[i]);
        System.out.println();
    }
    else
    {
        //还有更多个元素,递归产生排列
        for(int i=k;i<=m;i++)
        {
            MyMath.swap(List,k,i);
            perm(List,k+1,m);
            MyMath.swap(List,k,i);
        }
    }
}
/*============================================================================================
算法perm(list,k,m)递归地产生所有前缀是list[0:k-1]且后缀是list[k:m]的全排列的所有排列。
调用算法perm(list,0,n-1)则产生list[0:n-1]的全排列。
在一般情况下,k<m。算法将list[k:m]中每一个元素分别与list[k]中的元素交换,然后递归地计算list[k+1:m]的全排列,
并将结果作为list[0:k]的后缀。
MyMath.swap()用于交换两个表元素值。
==============================================================================================
*/
其实这个算法和上述第二段代码是一个道理。

 

不管如何修改,采用递归的设计方法实现的全排列,效率都不高。下面看看书上另外写的非递归代码。

 (下次再见呵呵)

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章