0

here で説明されている辞書順で一意の順列を生成するアルゴリズムを実装しようとしています。以下は私の実装です。

void My_Permute(string word) {
    sort(word.begin(),word.end());
    int size = word.size(); 
    while (true) {
        cout << word << endl;
        int i = size - 2;  
        for (; i >= 0; --i) { 
            if (word[i] < word[i+1]) break; 
        } 
        if (i <= -1) break; 
        swap(word[i],word[i+1]);
        cout << word << endl;
        reverse(word.begin()+i+1,word.end());
    } 
}

アルゴリズムは正しいと確信していますが、実装の何が問題なのですか? 私の機能はいくつかの順列を欠いています。以下は、入力の std::next_permutation と比較した私の出力を示していますabcd。

My_Permute             std::next_permutation
abcd                   abcd
abdc                   abdc
abdc                   acbd
adbc                   adbc
adcb                   adcb
dacb                   bacd
dbca                   bcad
dcba                   bcda
dcab                   bdac
dcba                   bdca
dcba                   cabd
                       cadb
                       cbad
                       ...
4

1 に答える 1

2

リンクされたアルゴリズムのステップ 2 がありません

void Permute(string word) {
    sort(word.begin(), word.end());
    int size = word.size();
    while (true) {
        cout << word << endl;
        // Find the largest index k such that a[k] < a[k + 1].
        // If no such index exists, the permutation is the last permutation.
        int i = size - 2;
        for (; i >= 0; --i) {
            if (word[i] < word[i+1])
                break;
        }
        if (i < 0)
            break;
        // Find the largest index l such that a[k] < a[l].
        // Since k + 1 is such an index, l is well defined and satisfies k < l.
        int j = size - 1;
        for (; ; --j) {
            if (word[i] < word[j])
                break;
        }
        // Swap a[k] with a[l].
        swap(word[i], word[j]);
        // Reverse the sequence from a[k + 1] up to and including the
        // final element a[n].
        reverse(word.begin() + i + 1, word.end());
    }
}

出力は次のとおりです。

abcd
abdc
acbd
acdb
adbc
adcb
bacd
badc
bcad
bcda
bdac
bdca
cabd
cadb
cbad
cbda
cdab
cdba
dabc
dacb
dbac
dbca
dcab
dcba

予想どおり、24 (つまり 4!) 行

ちなみに、「名前空間 std の使用」は極力避けるべきです。

于 2013-03-12T06:00:18.927 に答える