前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >全排列(递归与非递归实现)[通俗易懂]

全排列(递归与非递归实现)[通俗易懂]

作者头像
全栈程序员站长
发布2022-07-07 19:08:06
5980
发布2022-07-07 19:08:06
举报

大家好,又见面了,我是全栈君。

全排列问题在公司笔试的时候非经常见,这里介绍其递归与非递归实现。

递归算法

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.依次递归进行。

代码语言:javascript
复制
void swap(string &pszStr,int k,int m){	if(k==m)		return ;	char tmp;	tmp=pszStr[k];	pszStr[k]=pszStr[m];	pszStr[m]=tmp;}void  Perm( string &pszStr , int begin , int end ) {       if (begin == end)         {              static int s_i = 1;             cout<<" 第 "<<s_i ++<<" 个排列  "<<pszStr<<endl;      }        else      {              for (int i = begin; i <= end; i++) //第i个数分别与它后面的数字交换就能得到新的排列           {                    swap(pszStr,begin,i);                    Perm(pszStr, begin + 1, end);                    swap(pszStr , begin,  i);              }        }  }

非递归算法

1.算法简述

算法的具体描写叙述请參照此链接,写的很好。 http://blog.csdn.net/cpfeed/article/details/7376132

代码语言:javascript
复制
Prem( char *s )   //全排列函数{    char *pEnd = s + strlen(s) - 1;    char *p = pEnd;  //p代表替换点    //q代表替换点的下一个数 ,pMax 代表替换点后比替换点大的最小数    char *q = new char,*pMax = new char;  //注意初始化。!!    while (p !=  s)          //p == s 就结束循环    {        q = p;        p--;        if (*p < *q)        {            pMax = FindMaxForOne(p,pEnd);  //找与替换点交换的点            Swap(p,pMax);         //交换            Reverse(q,pEnd);       //将替换点后全部数进行反转            Print(s);              //输出            p = pEnd;             //将替换点置最后一个点。開始下一轮循环        }        if (s == p) break;           //结束条件    }}
代码语言:javascript
复制
char* FindMaxForOne(char *p,char *q)
{
    char *p1 = p;
    char *p2 = q;
    while (*p2 <= *p1) p2--;
    return p2;
}

发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/116403.html原文链接:https://javaforall.cn

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2022年1月2,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 递归算法
    • 1、算法简述
    • 非递归算法
    领券
    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档