[互联网面试笔试汇总C/C++-11] 字符串全排列和组合算法
全排列在笔试面试中很热门，因为它难度适中，既可以考察递归实现，又能进一步考察非递归的实现，便于区分出考生的水平。所以在百度和迅雷的校园招聘以及程序员和软件设计师的考试中都考到了，因此本文对全排列作下总结帮助大家更好的学习和理解。对本文有任何补充之处，欢迎大家指出。
首先来看看题目是如何要求的（百度迅雷校招笔试题）。
一、字符串的排列
用C++写一个函数, 如 Foo(const char *str), 打印出 str 的全排列,
如 abc 的全排列: abc, acb, bca, dac, cab, cba
一、全排列的递归实现
为方便起见，用123来示例下。123的全排列有123、132、213、231、312、321这六种。首先考虑213和321这二个数是如何得出的。显然这二个都是123中的1与后面两数交换得到的。然后可以将123的第二个数和每三个数交换得到132。同理可以根据213和321来得231和312。因此可以知道——全排列就是从第一个数字起每个数分别与它后面的数字交换。找到这个规律后，递归的代码就很容易写出来了：
[cpp]
#include<iostream>
using namespace std;
#include<assert.h>
void Permutation(char* pStr, char* pBegin)
{
assert(pStr && pBegin);
if(*pBegin == '\0')
printf("%s\n",pStr);
else
{
for(char* pCh = pBegin; *pCh != '\0'; pCh++)
{
swap(*pBegin,*pCh);
Permutation(pStr, pBegin+1);
swap(*pBegin,*pCh);
}
}
}
int main(void)
{
char str[] = "abc";
Permutation(str,str);
return 0;
}
另外一种写法：
[cpp]
//k表示当前选取到第几个数，m表示共有多少个数
void Permutation(char* pStr,int k,int m)
{
assert(pStr);
if(k == m)
{
static int num = 1; //局部静态变量，用来统计全排列的个数
printf("第%d个排列\t%s\n",num++,pStr);
}
else
{
for(int i = k; i <= m; i++)
{
swap(*(pStr+k),*(pStr+i));
Permutation(pStr, k + 1 , m);
swap(*(pStr+k),*(pStr+i));
}
}
}
int main(void)
{
char str[] = "abc";
Permutation(str , 0 , strlen(str)-1);
return 0;
}
如果字符串中有重复字符的话，上面的那个方法肯定不会符合要求的，因此现在要想办法来去掉重复的数列。
二、去掉重复的全排列的递归实现
由于全排列就是从第一个数字起每个数分别与它后面的数字交换。我们先尝试加个这样的判断——如果一个数与后面的数字相同那么这二个数就不交换了。如122，第一个数与后面交换得212、221。然后122中第二数就不用与第三个数交换了，但对212，它第二个数与第三个数是不相同的，交换之后得到221。与由122中第一个数与第三个数交换所得的221重复了。所以这个方法不行。
换种思维，对122，第一个数1与第二个数2交换得到212，然后考虑第一个数1与第三个数2交换，此时由于第三个数等于第二个数，所以第一个数不再与第三个数交换。再考虑212，它的第二个数与第三个数交换可以得到解决221。此时全排列生成完毕。
这样我们也得到了在全排列中去掉重复的规则——去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换。下面给出完整代码：
[cpp]
#include<iostream>
using namespace std;
#include<assert.h>
//在[nBegin,nEnd)区间中是否有字符与下标为pEnd的字符相等
bool IsSwap(char* pBegin , char* pEnd)
{
char *p;
for(p = pBegin ; p < pEnd ; p++)
{
if(*p == *pEnd)
return false;
}
return true;
}
void Permutation(char* pStr , char *pBegin)
{
assert(pStr);
if(*pBegin == '\0')
{
static int num = 1; //局部静态变量，用来统计全排列的个数
printf("第%d个排列\t%s\n",num++,pStr);
}
else
{
for(char *pCh = pBegin; *pCh != '\0'; pCh++) //第pBegin个数分别与它后面的数字交换就能得到新的排列
{
if(IsSwap(pBegin , pCh))
{
swap(*pBegin , *pCh);
Permutation(pStr , pBegin + 1);
swap(*pBegin , *pCh);
}
}
}
}
int main(void)
{
char str[] = "baa";
Permutation(str , str);
return 0;
}
OK，到现在我们已经能熟练写出递归的方法了，并且考虑了字符串中的重复数据可能引发的重复数列问题。那么如何使用非递归的方法来得到全排列了？
三、全排列的非递归实现
要考虑全排列的非递归实现，先来考虑如何计算字符串的下一个排列。如"1234"的下一个排列就是"1243"。只要对字符串反复求出下一个排列，全排列的也就迎刃而解了。
如何计算字符串的下一个排列了？来考虑"926520"这个字符串，我们从后向前找第一双相邻的递增数字，"20"、"52"都是非递增的，"26 "即满足要求，称前一个数字2为替换数，替换数的下标称为替换点，再从后面找一个比替换数大的最小数（这个数必然存在），0、2都不行，5可以，将5和2交换得到"956220"，然后再将替换点后的字符串"6220"颠倒即得到"950226"。
对于像“4321”这种已经是最“大”的排列，采用STL中的处理方法，将字符串整个颠倒得到最“小”的排列"1234"并返回false。
这样，只要一个循环再加上计算字符串下一个排列的函数就可以轻松的实现非递归的全排列算法。按上面思路并参考STL中的实现源码，不难写成一份质量较高的代码。值得注意的是在循环前要对字符串排
补充：软件开发 , C语言 ,
