对于像“4321”这种已经是最“大”的排列，采用STL中的处理方法，将字符串整个颠倒得到最“小”的排列"1234"并返回false。

这样，只要一个循环再加上计算字符串下一个排列的函数就可以轻松的实现非递归的全排列算法。按上面思路并参考STL中的实现 源码，不难写成一份质量较高的代码。值得注意的是在循环前要对字符串排序下，可以自己写快速排序的代码（请参阅《白话经典算法之六 快速排序 快速搞定》），也可以直接使用VC库中的快速排序函数（请参阅《使用VC库函数中的快速排序函数》）。下面列出完整代码：

[cpp]

#include

#include

#include

using namespace std;

#include

//反转区间

void Reverse(char* pBegin , char* pEnd)

{

while(pBegin < pEnd)

swap(*pBegin++ , *pEnd--);

}

//下一个排列

bool Next_permutation(char a[])

{

assert(a);

char *p , *q , *pFind;

char *pEnd = a + strlen(a) - 1;

if(a == pEnd)

return false;

p = pEnd;

while(p != a)

{

q = p;

p--;

if(*p < *q) //找降序的相邻2数,前一个数即替换数

{

//从后向前找比替换点大的第一个数

pFind = pEnd;

while(*pFind < *p)

--pFind;

swap(*p , *pFind);

//替换点后的数全部反转

Reverse(q , pEnd);

return true;

}

}

Reverse(a , pEnd); //如果没有下一个排列,全部反转后返回false

return false;

}

int cmp(const void *a,const void *b)

{

return int(*(char *)a - *(char *)b);

}

int main(void)

{

char str[] = "bac";

int num = 1;

qsort(str , strlen(str),sizeof(char),cmp);

do

{

printf("第%d个排列\t%s\n",num++,str);

}while(Next_permutation(str));

return 0;

}

至此我们已经运用了递归与非递归的方法解决了全排列问题，总结一下就是：

1、全排列就是从第一个数字起每个数分别与它后面的数字交换。

2、去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换。

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

二、字符串的组合

题目：输入一个字符串，输出该字符串中字符的所有组合。举个例子，如果输入abc，它的组合有a、b、c、ab、ac、bc、abc。

上面我们详细讨论了如何用递归的思路求字符串的排列。同样，本题也可以用递归的思路来求字符串的组合。

假设我们想在长度为n的字符串中求m个字符的组合。我们先从头扫描字符串的第一个字符。针对第一个字符，我们有两种选择：第一是把这个字符放到组合中去，接下来我们需要在剩下的n-1个字符中选取m-1个字符；第二是不把这个字符放到组合中去，接下来我们需要在剩下的n-1个字符中选择m个字符。这两种选择都很容易用递归实现。下面是这种思路的参考代码：

[cpp]

#include

#include

#include

using namespace std;

#include

void Combination(char *string ,int number,vector &result);

void Combination(char *string)

{

assert(string != NULL);

vector result;

int i , length = strlen(string);

for(i = 1 ; i <= length ; ++i)

Combination(string , i ,result);

}

void Combination(char *string ,int number , vector &result)

{

assert(string != NULL);

if(number == 0)

{

static int num = 1;

printf("第%d个组合\t",num++);

vector::iterator iter = result.begin();

for( ; iter != result.end() ; ++iter)

printf("%c",*iter);

printf("\n");

return ;

}

if(*string == '\0')

return ;

result.push_back(*string);

Combination(string + 1 , number - 1 , result);

result.pop_back();

Combination(string + 1 , number , result);

}

int main(void)

{

char str[] = "abc";

Combination(str);

return 0;

}

由于组合可以是1个字符的组合，2个字符的字符……一直到n个字符的组合，因此在函数void Combination(char* string)，我们需要一个for循环。另外，我们用一个vector来存放选择放进组合里的字符。

方法二：用位运算来实现求组合

[cpp]

#include

using namespace std;

int a[] = {1,3,5,4,6};

char str[] = "abcde";

void print_subset(int n , int s)