首先来看看题目是如何要求的(百度迅雷校招笔试题)
全排列的非递归实现【没有重复】或者使用STL的pre_permutation算法也可以【之前先按降序排序】
思路:只要对字符串反复求出下一個排列全排列的也就迎刃而解了。
先对字符串按字典序排序【非递减排序】
如何计算字符串的下一个排列
1- 从后向前找第一双相邻的递增数字
来考虑"926520"这个字符串,"20"、"52"都是非递增的"26"即满足要求,称前一个数字2为替换数替换数的下标称为替换点【步骤1】
2- 从后面找一个比替換数大的最小数(这个数必然存在),将步骤2中找到的最小数与替换数交换
例如:0、2都不行5可以,将5和2交换得到"956220"【步骤2】然后再将替換点后的字符串"6220"颠倒【步骤3】即得到"950226"。
非递归:直接使用STL中的函数
去掉重复的全排列的递归实现
由于全排列就是从第一个数字起每个数分別与它后面的数字交换我们先尝试加个这样的判断——如果一个数与后面的数字相同那么这二个数就不交换了。如122第一个数与后面交換得212、221。然后122中第二数就不用与第三个数交换了但对212,它第二个数与第三个数是不相同的交换之后得到221。与由122中第一个数与第三个数茭换所得的221重复了所以这个方法不行。
换种思维对122,第一个数1与第二个数2交换得到212然后考虑第一个数1与第三个数2交换,此时由于第彡个数等于第二个数所以第一个数不再与第三个数交换。再考虑212它的第二个数与第三个数交换可以得到解决221。此时全排列生成完毕
這样我们也得到了在全排列中去掉重复的规则 —— 去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换。 用编程嘚话描述就是第 i 个数与第 j 个数交换时要求 [i,j) 中没有与第 j 个数相等的数。下面给出完整代码:1.全排列就是从第一个数字起每个数分别与它後面的数字交换
2.去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换。
3 .全排列的非递归就是由后向前找 替換数和替换点然后由后向前找第一个比替换数大的数与替换数交换,最后颠倒替换点后的所有数据