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

全排列在近几年各大网络公司的笔试中出现的比较频繁 首先来看看题目是如何要求的(百度迅雷校招笔试题)。 用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、代码参考

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

3、见图知晓

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

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

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

1bool IsSwap(char *pszStr, int nBegin, int nEnd)  
2{  
3       for (int i = nBegin; i < nEnd; i++) 
4           if (pszStr[i] == pszStr[nEnd])  
5                 return false;  
6       return true;  
7}

所以,改进的代码如下:

 1Perm(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、代码分析

 1Prem( 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) 
20        break;           //结束条件
21    }
22}

上面涉及到几个函数 说一下找与替换数交换的数的函数

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

关键是掌握上面两种!

四、总结

至此我们已经运用了递归与非递归的方法解决了全排列问题,总结一下就是: 1.全排列就是从第一个数字起每个数分别与它后面的数字交换。 2.去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换。 3.全排列的非递归就是由后向前找替换数和替换点,然后由后向前找第一个比替换数大的数与替换数交换,最后颠倒替换点后的所有数据。

本文由aCloudDeveloper投稿

原文发布于微信公众号 - 高性能服务器开发(easyserverdev)

原文发表时间:2018-05-31

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏owent

C/C++语言常用排序算法

资料由互联网收集整理,供新手参考学习 这里又生动点的演示:http://www.cnblogs.com/wangfupeng1988/archive/2011...

12410
来自专栏CDA数据分析师

Python面试中8个必考问题

1、下面这段代码的输出结果是什么?请解释。 ? 怎样修改extendList的定义能够产生以下预期的行为? 上面代码输出结果将是: ? 很多人都会误认为list...

205100
来自专栏北京马哥教育

从Zero到Hero,一文掌握Python关键代码

本文整体梳理了 Python 的基本语法与使用方法,并重点介绍了对机器学习十分重要且常见的语法,如基本的条件、循环语句,基本的列表和字典等数据结构,此外还介绍...

32170
来自专栏QQ音乐前端团队专栏

理解浮点数

相信大家在平常的 JavaScript 开发中,都有遇到过浮点数运算精度误差的问题。

73940
来自专栏木子昭的博客

正则 (入门篇)简单来说写好正则表达式的两个要点:写在最后

如果你对正则感兴趣,读完这篇文章,一定会有收获~_^ 简单来说 正则一般代指正则表达式 正则表达式是从"复杂数据"中抽取"有用数据"的公式 ---- 写好正则...

31380
来自专栏小樱的经验随笔

【批处理学习笔记】第十七课:截取字符串

    在批处理中,set的功能有点繁杂:设置变量、显示环境变量的名及值、做算术运算、等待用户的输入、字符串截取、替换字符串,是我们常用的命令之一。   在字...

33340
来自专栏测试开发架构之路

总结了一些指针易出错的常见问题(二)

4.指针与数组    一些常见的错误观点是数组和指针是完全可以互换的。尽管数组名字有时候可以当指针来使用,但是数组的名字不是指针。 数组是能用索引访问的同质元...

36070
来自专栏个人随笔

Java 使用面向对象开发

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

33370
来自专栏小詹同学

Leetcode打卡 | No.27 移除元素

欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!这个记录帖哪怕只有一个读者,小詹也会坚持刷下去的!

7310
来自专栏老九学堂

【学习】Java微课堂之for循环

主要知识点 ? ? for循环注意要点 本讲视频中讲了for循环的要点以及三大循环的区别,主要笔记如下: 1.for循环是循环控制结构中使用最广泛的一种循环控制...

33560

扫码关注云+社区

领取腾讯云代金券