转自： http://blog.csdn.net/wuzhekai1985
问题1 ：输入一个字符串，打印出该字符串中字符的所有排列。例如输入字符串abc，则输出由字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab和cba。
思路：这是个递归求解的问题。递归算法有四个特性：（1)必须有可达到的终止条件，否则程序将陷入死循环；（2）子问题在规模上比原问题小；（3）子问题可通过再次递归调用求解；（4）子问题的解应能组合成整个问题的解。
对于字符串的排列问题。如果能生成n - 1个元素的全排列，就能生成n个元素的全排列。对于只有1个元素的集合，可以直接生成全排列。全排列的递归终止条件很明确，只有1个元素时。下面这个图很清楚的给出了递归的过程。
参考代码：解法1通过Permutation_Solution1(str, 0, n); 解法2通过调用Permutation_Solution2(str, str)来求解问题。
- //函数功能 ： 求一个字符串某个区间内字符的全排列
- //函数参数 ： pStr为字符串，begin和end表示区间
- //返回值 ： 无
- void Permutation_Solution1(char *pStr, int begin, int end)
- {
- if(begin == end - 1) //只剩一个元素
- {
- for(int i = 0; i < end; i++) //打印
- cout<<pStr[i];
- cout<<endl;
- }
- else
- {
- for(int k = begin; k < end; k++)
- {
- swap(pStr[k], pStr[begin]); //交换两个字符
- Permutation_Solution1(pStr, begin + 1, end);
- swap(pStr[k],pStr[begin]); //恢复
- }
- }
- }
- //函数功能 ： 求一个字符串某个区间内字符的全排列
- //函数参数 ： pStr为字符串，pBegin为开始位置
- //返回值 ： 无
- void Permutation_Solution2(char *pStr, char *pBegin)
- {
- if(*pBegin == '\0')
- {
- cout<<pStr<<endl;
- }
- else
- {
- char *pCh = pBegin;
- while(*pCh != '\0')
- {
- swap(*pBegin, *pCh);
- Permutation_Solution2(pStr, pBegin + 1);