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

全排列(递归与非递归实现)

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

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

递归算法

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

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

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; //结束条件 }}

char* FindMaxForOne(char *p,char *q)
{
    char *p1 = p;
    char *p2 = q;
    while (*p2 <= *p1) p2--;
    return p2;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

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

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • SpringMVC工作原理及其流程

    SpringMVC工作原理及其流程本文介绍SpringMVC的基本原理,对于一个浏览器请求,SpringMVC的处理流程。SpringMVC主要包含一下组件DispatcherServlet-前端控制器HandlerMapping-处理器映射Controller-控制器ViewResolver-视图解析器View-视图Spring的请求流程SpringMVC的核心在于其请求流程,这是使用Spring…

  • centos7安装python3.7_python软件安装步骤

    centos7安装python3.7_python软件安装步骤Centos7安装Python3.8详细教程Centos7安装Python3.8详细教程安装编译相关工具下载python安装包编译安装python创建软连接更改yum配置Centos7安装Python3.8详细教程安装编译相关工具yum-ygroupinstall”Developmenttools”yum-yinstallzlib-develbzip2-developenssl-develncurses-develsqlite-develreadline-develtk-d

  • 基础的递归数列「建议收藏」

    基础的递归数列「建议收藏」/*copyright(c)2013,烟台大学计算机学院*Allrightsreserved.*作者:赵振凯*完成日期:2013年11月20日*版本号:v1.0*问题描述:基础的递归数列*/#includeusingnamespacestd;voidf(int);intmain(){inti=1234;f(i);re

  • System.err.println()和System.out.println()区别

    System.err.println()和System.out.println()区别看了些资料总结下:1.JDK文档对两者的解释:out:“标准”输出流。此流已打开并准备接受输出数据。通常,此流对应于显示器输出或者由主机环境或用户指定的另一个输出目标。err:“标准”错误输出流。此流已打开并准备接受输出数据。通常,此流对应于显示器输出或者由主机环境或用户指定的另一个输出目标。按照惯例,此输出流用于显示错误消息,或者显示那些即使用户输出流(变量 out 的值)已经重定向…

  • ftp登陆命令「建议收藏」

    ftp登陆命令「建议收藏」 一、shelll示例:cd/PATH_YOU_WANT_TO_UPLOAD(DOWNLOAD)ftp-niv&amp;lt;&amp;lt;-EOFopenIP_ADDRESSuserUSERNAMEPASSWORDascii(orbin)put*(orget)byeEOF下面详细讲解以下这段代码:&amp;nbsp;&amp;nbsp;&amp;nb…

  • mybatis缓存配置

    mybatis缓存配置mybatis的缓存有三种方式:1、一级缓存(基于SqlSession会话级别的;2、二级缓存(基于nameSpace级别的,范围比以及缓存更广);3、第三方缓存;mybatis缓存使示意图:一、一级缓存说明:其中一级缓存是mybatis默认使用的缓存,无需手动配置,二级缓存需要手动配置;一级缓存失效条件1)sqlSession不同,由于一级缓存是基于sqlSession级别的,所以当使用不同sq…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号