c++ - 字符串实现的排列问题

Question

我正在研究字符串问题的所有排列。目前，我正在使用一个 char 列表来表示一个字符串。字符列表的列表将表示所有可能的排列。

算法非常简单。对于每个长度为 n 的字符串，您可能希望砍掉第一个字母并找到 n-l 字符串的所有排列。然后你会在较小的字符串的每个地方插入第一个字母。插入第一个字母导致运行时异常，我似乎无法弄清楚在哪里。

main.cpp

#include <vector>
#include <list>

using namespace std;

int main (void){

    list<char> s;

    s.push_back('f');
    s.push_back('c');
    s.push_back('g');

    list<list<char> > mylist;
    list<char>::iterator vit;
    list<char> myvector;
    mylist = perm(s,mylist);


    for(list<list<char> >::iterator it = mylist.begin(); it != mylist.end(); ++it){
        myvector = *it;
        for(vit = myvector.begin(); vit != myvector.end(); ++vit){
            cout << *vit << " ";
        }
        cout << "\n" << endl;
    }

    getchar();
    return 0;   
}

实现:

list<list <char> > perm(list<char> s, list<list<char> > mylist){
    int n = s.size();

    if(n == 1){
        mylist.push_back(s);
        return mylist;

    }

    else{
        list<char>::iterator vit = s.begin();
        char first = *vit;
        s.erase(vit);        

        list<list<char> > listB = perm(s,mylist);

        for(list<list<char> >::iterator it = listB.begin(); it != listB.end(); ++it){
            list<char> myvector = *it;
            for(list<char>::iterator vit2 = myvector.begin(); vit != myvector.end(); ++vit){
                cout << *vit2 << endl;
                vit2 = myvector.insert(vit2,first);
                cout << *vit2 << endl;
                mylist.push_back(myvector);
                myvector.erase(vit2);
            }
        }

        return mylist;
    }

}

输出:

                g
                c
                c
                f
                f

然后是运行时异常。

Answer 1

tl;博士

只需使用std::next_permutation。