今天学习了字符串全排列问题的递归与非递归实现，其中，递归实现是把递归放在循环中，到现在我也没看懂到底是个什么样的过程。不过非递归的算法倒是看懂了，终于理解了一句话：如果算法思路有了，实现根本就不是问题。可我们常常做的一件事就是思路并不怎么清晰，就开始写代码，然后通过一点点调试直到正确。其实这样是不对的，以后要端正编码的态度，思路完全清晰了才能开始写代码。好了，扯了一堆废话，下面开始正题吧。
首先，所谓字符串全排列问题，就是给定一个字符串，写出以该字符串生成的所有排列的字符串。例如abc，通过全排列可以生成6个字符串:abc,acb,bac,bca,cba,cab。
先说一下它的非递归算法的思路：
1.先将字符串中的字符从下到大排序。
2.从后往前找到第一个相邻的递增字符对，设该字符对中的第一个叫替换数A，其位置（下标）叫做替换点a，然后我们从后往前找到第一个大于A的字符B,交换A和B，让后将位置a之后的字符串颠倒。
3.这样重复操作(通过传引用实现)，知道字符串中再也找不到相邻的递增字符对，表示全排列已经结束了.
题目：字符串的排列
题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
代码：
class Solution {
public:
bool hasNext(string& str){
if(str.size() < 2)
return false;
int pos = str.size() - 2;
while(pos >= 0){//找替换数
if(str[pos] >= str[pos + 1])
pos --;
else
break;
}
if(pos == -1)//表示所有相邻字符对都是递减的了，全排列结束
return false;
char val = str[pos];
int i = str.size() - 1;
for(; i > pos; i --){//找替换点后面第一个大于替换数的数
if(val < str[i])
break;
}
swap(str[pos], str[i]);
int start = pos + 1;
int last = str.size() - 1;
while(start < last)//将替换点后的字符串颠倒
swap(str[start ++], str[last --]);
return true;
}
vector<string> Permutation(string str) {
vector<string> ret;
if(str.size() == 0)
return ret;
sort(str.begin(), str.end());
ret.push_back(str);
while(hasNext(str)){
ret.push_back(str);//传引用
}
return ret;
}
};
