5

以下は、指定された文字列のすべての順列を出力するコードです。コードはコンパイルされますが、何も出力されません。

using namespace std;

void RecPermute(string, string);

int main() {
    RecPermute("", "abc");
    return 0;
}

void RecPermute(string soFar, string rest) {
    if (rest == " ") {
        cout << soFar << endl;
    } else {
        for(int i=0; i<rest.length(); i++) {
            string next = soFar + rest[i];
            string remaining = rest.substr(0, i) + rest.substr(i+1);
            RecPermute(next, remaining);
    }
    }
}

何を修正する必要がありますか?

4

2 に答える 2

18

あなたのアプローチは（greedybuddhaが提供する正しい条件で）機能しますが、はるかに簡単に実現できます（chrisが示唆するように）。

#include <algorithm>
#include <iostream>
#include <string>

int main()
{
    std::string s("abcdefg");
    do
    {
        std::cout << s << "\n";
    }
    while ( std::next_permutation(s.begin(), s.end()) );
}

さて、それは何をしますか？std::next_permutation1 つは文字列の先頭、2 番目は末尾なので、基本的には「文字列全体を考慮してください」と言っています。呼び出しの後に、 の直前の値の直後に辞書式順序で表示される一意の順列が含まれるsように、文字列を並べ替えます。が最後のそのような順列 (つまり、入力 "abcdefg" に対する "gfedcba") である場合は、戻ります。したがって、完了したことがわかります。sssstd::next_permutationfalse

このコードでは新しい (一時的な) 文字列を作成していないため、読みやすくなるだけでなく、高速になります。私のマシンでは、あなたのアルゴリズムは「abcdefghij」に約 5 秒かかり、使用したアルゴリズムは 1 秒std::next_permutation未満で終了します。別のキャラクターでは、6.8 秒に対して 54 秒に悪化します。

最初の文字列がソートされていない場合、順列の完全なリストが得られないことに注意してください。しかしもちろん、これには簡単な解決策があります: 順列のstd::sort(s.begin(), s.end());前に実行します。

于 2013-06-09T06:27:08.367 に答える
1

だから、あなたはとても興味をそそるほど近くにいます。スペースではなく空の文字列が一致する場合にのみ必要です。これは、空の文字列を照合することで実行できます""。

変化する 

if (rest == " ") { ... }

に

if (rest == "") { ... }

そして、rest.substr(i+1) の長さを忘れました。(i+1,i-3); のはずです。

于 2013-06-09T05:45:56.130 に答える