字符串全排列问题

今天学习了字符串全排列问题的递归与非递归实现，其中，递归实现是把递归放在循环中，到现在我也没看懂到底是个什么样的过程。不过非递归的算法倒是看懂了，终于理解了一句话：如果算法思路有了，实现根本就不是问题。可我们常常做的一件事就是思路并不怎么清晰，就开始写代码，然后通过一点点调试直到正确。其实这样是不对的，以后要端正编码的态度，思路完全清晰了才能开始写代码。好了，扯了一堆废话，下面开始正题吧。

首先，所谓字符串全排列问题，就是给定一个字符串，写出以该字符串生成的所有排列的字符串。例如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;
    }
};