next_permutation的源代码解析

一、迭代写法

• 算法来自STL源代码

bool myNext( string::iterator First, string::iterator Last )
{
    if( First==Last )
    {
        return false;
    }
    string::iterator temp=First;
    ++temp;
    if( temp==Last )
    {
        return false;
    }

    string::iterator two=Last;
    --two;
    string::iterator one=Last;
    --one;
    --one;
    //逆向思维：从后往前，找到2个相邻的，第1个满足*one < *two的
    while( !(*one < *two) )
    {
        if( First==one )
        { 
            reverse( First, Last );
            return false;
        }
        --one;
        --two;
    }
    //准备一个临时iterator从后往前，找到 第1个*one < *solve
    string::iterator solve=Last;
    --solve;
    while( !(*one < *solve ) )
    {
        --solve;
    }

    //交换迭代器
    iter_swap( one, solve );
    //将迭代器two及其后面的全部反转『重要』
    reverse( two, Last);
    return true;

}
class Solution {
public:
    vector<string> Permutation(string str) {
        vector<string> ret;
        do
        {
            ret.push_back( str );
        }while( myNext( str.begin(), str.end() ) );
        return ret;
    }
};

二、STL写法

class Solution {
public:
    vector<string> Permutation(string str) {
        vector<string> ret;
        do
        {
            ret.push_back( str );
        }while( next_permutation( str.begin(), str.end() ) );
        return ret;
    }
};