全排列(含递归和非递归的解法)

全排列在近几年各大网络公司的笔试中出现的比较频繁

首先来看看题目是如何要求的。

用C++写一个函数, 如 Foo(const char *str), 打印出 str 的全排列,

如 abc 的全排列: abc, acb, bca, dac, cab, cba

一、      递归版本

1、算法简述

简单地说:就是第一个数分别以后面的数进行交换

E.g:E = (a , b , c),则 prem(E)= a.perm(b,c)+ b.perm(a,c)+ c.perm(a,b)

然后a.perm(b,c)= ab.perm(c)+ ac.perm(b)= abc + acb.依次递归进行

好了,知道算法之后就不难编出一份好的代码了。

2、代码参考

1 Foo(const char *str)
2 {
3     Perm( str , 0 , strlen( str ) – 1 );
4 }
 1 //需要三个参数,k表示当前的数,m表示数的个数
 2 Perm( char *pszStr , int k , int m ) 
 3 {
 4       if (k == m)  
 5       {  
 6            static int s_i = 1;  
 7            cout<<” 第 ”<<s_i ++<<” 个排列  ”<<pszStr<<endl;
 8      }  
 9      else
10      {  
11            for (int i = k; i <= m; i++) //第i个数分别与它后面的数字交换就能得到新的排列
12            {  
13                   Swap(pszStr + k, pszStr + i);  
14                   Perm(pszStr, k + 1, m);  
15                   Swap(pszStr + k, pszStr + i);  
16            }  
17       } 
18 }

3、见图知晓

不过这样存在一点小小的缺陷:两个相同的数也进行了交换,见下图:

明显,这绝对不符合要求:

4、代码改进

去掉重复符号的全排列:在交换之前可以先判断两个符号是否相同,不相同才交换,这个时候需要一个判断符号是否相同的函数。

bool IsSwap(char *pszStr, int nBegin, int nEnd)  
{  
       for (int i = nBegin; i < nEnd; i++) 
       if (pszStr[i] == pszStr[nEnd])  
             return false;  
       return true;  
}  

所以,改进的代码如下:

 1 Perm(char *pszStr, int k, int m)  
 2 {  
 3      if (k == m)  
 4      {  
 5           Static int s_i = 1;  
 6           cout<<” 第 ”<<s_i ++<<” 个排列  ”<<pszStr<<endl;
 7      }  
 8      else
 9      {  
10           for (int i = k; i <= m; i++) //第i个数分别与它后面的数字交换就能得到新的排列
11           {  
12                 if (IsSwap(pszStr, k, i))   //添加的判断语句,判断是否相等
13                 {  
14                       Swap(pszStr + k, pszStr + i);  
15                       Perm(pszStr, k + 1, m);  
16                       Swap(pszStr + k, pszStr + i);  
17                 }  
18            }  
19       }  
20 }  

OK,见图知情况

 二、 非递归版本

1、算法简述

要考虑全排列的非递归实现,先来考虑如何计算字符串的下一个排列。如"1234"的下一个排列就是"1243"。只要对字符串反复求出下一个排列,全排列的也就迎刃而解了。

如何计算字符串的下一个排列了?来考虑"926520"这个字符串,我们从后向前找第一双相邻的递增数字,"20"、"52"都是非递增的,"26 "即满足要求,称前一个数字2为替换数,替换数的下标称为替换点,再从后面找一个比替换数大的最小数(这个数必然存在),0、2都不行,5可以,将5和2交换得到"956220",然后再将替换点后的字符串"6220"颠倒即得到"950226"。

如果达到这个数的最大,比如1234-à4321,这个时候就结束整个循环。

如果输入是一个非最小数,如1324,则将它转换为最小数,如1234,再进行排序。排序算法用快排,可以自己写一个,如果快排不会的话,就先看会再来接着看,或者自己想一个靠谱的算法,也可以直接用VC库中的qsort(s , n , sizeof(s[0]) , cmp);各参数是什么意思就自己在下面多花点时间吧。

OK,下面看代码分析

2、代码分析

 1 Prem( char *s )   //全排列函数
 2 {
 3     char *pEnd = s + strlen(s) - 1;
 4     char *p = pEnd;  //p代表替换点
 5     //q代表替换点的下一个数 ,pMax 代表替换点后比替换点大的最小数
 6     char *q = new char,*pMax = new char;  //注意初始化!!!
 7     while (p !=  s)          //p == s 就结束循环
 8     {
 9         q = p;
10         p--;
11         if (*p < *q)
12         {
13             pMax = FindMaxForOne(p,pEnd);  //找与替换点交换的点
14             Swap(p,pMax);         //交换
15             Reverse(q,pEnd);       //将替换点后所有数进行反转
16             Print(s);              //输出
17             p = pEnd;             //将替换点置最后一个点,开始下一轮循环
18         }
19         if (s == p) break;           //结束条件
20     }
21 }

上面涉及到几个函数

说一下找与替换数交换的数的函数

1 char* FindMaxForOne(char *p,char *q)
2 {
3     char *p1 = p;
4     char *p2 = q;
5     while (*p2 <= *p1) p2--;
6     return p2;
7 }

!!!这里要说明:从后往前找的第一个比替换数大的数一定就是要找的最小数,Why,这个慢慢品味,我做的时候也遇到一定的困难,自己去做,不经历就不会轻易铭记。

其他函数简直就是小case了。祝君成功!

3、见图知晓

三、非递归还有一种方法

  描述:和上一种不同的是:这种算法比较笨,但很好理解,不用按照上一种那么严格从小到大进行排列输出。

  首先先将最后一个数从右往左依次交换输出,然后判断个数是否为基数,交换离该数最远端的两个数,再把第一个数从左往右交换输出,交换远端的两个数,如此进行循环就能排列完全部的数。这说得可能比较抽象,看一个例子:

  E.g:            1 2 3 4

第一次:(从右往左):1 2 4 3   ---  1 2 4 3 --- 1 4 2 3  ---  4 1 2 3   把最后一个数依次往前移

           交换:2 和 3  --->   4 1 3 2

第二次:(从左往右):4 1 3 2  ---  1 4 3 2  ---  1 3 4 2  ---  1 3 2 4  把第一个数依次往后移

           交换:1 和 3  ----> 3 1 2 4           重复第一次,知道把所有数输出为止

看代码:

 1 /************************************************************************
 2  *   Author: bakari 
 3  *   Date:   2011.5.7
 4 /************************************************************************/
 5 int n;
 6 void swap(int *a,int *b);    //交换函数 
 7 void print(int a[]);         //打印交换后的每一组数 
 8 int jfc();                   //求阶乘函数 
 9 int jmp(int n);              //跳转函数 
10 void sort(int a[]);          //全排列函数 
11 
12 int main(){
13     while(cin>>n)
14     {
15         while(n<=0)
16         {
17             cout<<"输入有误!请重新输入: ";
18             cin>>n;
19         }
20         int *a=new int[n];
21         for(int i=0;i<n;i++)
22             a[i]=i+1;
23         sort(a);
24         delete []a;
25     }
26     system("pause");
27     return 0;
28 }
29 
30 void swap(int *a,int *b)
31 {
32     int t=*a;
33     *a=*b;
34     *b=t;
35 }
36 void print(int a[])
37 {
38     for(int i=0;i<n;i++)
39         cout<<a[i]<<' '; 
40     cout<<endl;
41 
42 }
43 int jfc()
44 {
45     int s=1;
46     for(int i=1;i<=n;i++)
47         s*=i;
48     return s;
49 }
50 int jmp(int n)
51 {
52     if(n>jfc())
53         return 0;
54 }
55 void sort(int a[])
56 {
57     int m=1,count=0;                   //m统计全排列的个数,count统计行数 
58     int *p1,*p2;
59     for(p1=a+n-1,p2=a+n-2;p1>=a+1,p2>=a;p1--,p2--)
60     {
61         print(a);
62         swap(p1,p2);
63         m++;
64     } 
65     count++;
66     while(m<=jfc()){
67         if(count%2)
68         {   print(a);
69         swap(&a[n-1],&a[n-2]);
70         m++;
71         if(!jmp(m))
72             break;
73         for(p1=a,p2=a+1;p1<=a+n-2,p2<=a+n-1;p1++,p2++)
74         {
75             print(a);
76             swap(p1,p2);
77             m++;
78         }
79         count++;
80         }
81         else
82         {
83             print(a);
84             swap(&a[0],&a[1]);
85             m++;
86             if(!jmp(m))
87                 break;
88             for(p1=a+n-1,p2=a+n-2;p1>=a+1,p2>=a;p1--,p2--)
89             {
90                 print(a);
91                 swap(p1,p2);
92                 m++;
93             }
94             count++;
95         }
96 
97     } 
98     cout<<"共有"<<m-1<<"种排列"<<endl;
99 }    

关键是掌握上面两种!

四、   总结

至此我们已经运用了递归与非递归的方法解决了全排列问题,总结一下就是:

1.全排列就是从第一个数字起每个数分别与它后面的数字交换。

2.去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换。

3.全排列的非递归就是由后向前找替换数替换点,然后由后向前找第一个比替换数大的数与替换数交换,最后颠倒替换点后的所有数据。

                                                                                                                                                                      -----写于2012/8/2--23:48

                                                                                                                                                                              希望大家多多烧香!

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏布尔

想起温习一下JS中的this apply call arguments

很多时候讲到语言入门,大家会认为就是要了解一下语言的语法、数据类型和常用函数。这一课对于所有的计算机专业的毕业生来说都可以自学,然而在最近的实践中(带了两个实习...

21710
来自专栏个人随笔

Java 使用面向对象开发

对象就是实际存在的一些东西 程序来源于生活 软件出现的目的: 用计算机的语言描述现实世界 用计算机解决现实世界的问题 面向对象设计和开发程序的好处: 交流更加流...

3297
来自专栏前端黑板报

一个数字截取引发的精度问题(三)

上次总结的第四条: 当传入的参数小于数字的整数位时,返回指数形式表示的字符串。 let numObj = 12345.6numObj.toPrecision(2...

2048
来自专栏高性能服务器开发

全排列(含递归和非递归的解法)

全排列在近几年各大网络公司的笔试中出现的比较频繁 首先来看看题目是如何要求的(百度迅雷校招笔试题)。 用C++写一个函数, 如 Foo(const char *...

1713
来自专栏北京马哥教育

grep命令及正则表达式

grep基本概念 grep:global search regular expression and print out the line. 作用:文本过滤器,...

3647
来自专栏MyBlog

Effective.Java 读书笔记(4)非实例化

有时你想要编写一个类,这个类只是静态方法和静态域的组成,这样的一个类获得一个糟糕的名声因为一些人滥用他们为了避免对对象的术语进行思考,但是他们的确是有用的

862
来自专栏函数式编程语言及工具

泛函编程(13)-无穷数据流-Infinite Stream

    上节我们提到Stream和List的主要分别是在于Stream的“延后计算“(lazy evaluation)特性。我们还讨论过在处理大规模排列数据集时...

1925
来自专栏liulun

Nim教程【十】

openarray类型 注意:openarray类型只能用于参数 固定大小的数组虽然性能不错,但过于呆板,使用取来不是很方便 对于一个方法来说,传入参数如果是一...

2808
来自专栏彭湖湾的编程世界

【JavaScript】 JS面向对象的模式与实践

参考书籍 《JavaScript高级语言程序设计》—— Nicholas C.Zakas 《你不知道的JavaScript》  —— KYLE SIMPSON ...

3686
来自专栏技术专栏

Scala入门与进阶(五)- 模式匹配

871

扫码关注云+社区

领取腾讯云代金券