全排列

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

首先来看看题目是如何要求的（百度迅雷校招笔试题）。

用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、代码参考

3、见图知晓

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

明显，这绝对不符合要求：

4、代码改进

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

所以，改进的代码如下：

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

上面涉及到几个函数

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

！！！这里要说明：从后往前找的第一个比替换数大的数一定就是要找的最小数，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．去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换。

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

欢迎关注公众号『easyserverdev』。如果有任何技术或者职业方面的问题需要我提供帮助，可通过这个公众号与我取得联系，此公众号不仅分享高性能服务器开发经验和故事，同时也免费为广大技术朋友提供技术答疑和职业解惑，您有任何问题都可以在微信公众号直接留言，我会尽快回复您。