c++ - 实现词典排序以查找唯一排列

Question

我正在尝试实现一种算法，以描述 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());
    } 
} 

我确信算法是正确的，那么我的实现有什么问题呢？我的功能是遗漏一些排列。下面显示了我的输出与输入 abcd 上的 std::next_permutation 的比较。

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
                       ...

Answer 1

您缺少链接算法的第 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!)行，符合预期

顺便说一句，你应该avoid "using namespace std"尽可能多。