私は文字列問題のすべての順列に取り組んでいます。現在、文字列を表すためにcharのリストを使用しています。文字リストのリストは、考えられるすべての順列を表します。
アルゴリズムは非常に単純です。長さnの文字列ごとに、最初の文字を切り取り、nlの文字列のすべての順列を検索する必要があります。次に、小さい文字列のすべての場所に最初の文字を挿入します。ランタイム例外を発生させるために最初の文字を挿入すると、どこにあるのかわかりません。
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
次に、実行時例外。