全排列的递归与非递归实现浅析

全排列的递归与非递归实现浅析2014-12-25全排列问题在公司笔试的时候很常见，这里介绍其递归与非递归实现。

递归算法

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;}voidPerm（ 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;}