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

Question

我正在尝试实现一种算法，以按照此处描述的字典顺序生成唯一排列。以下是我的实现。

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

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！）行，如预期的那样

顺便说一句，您应该尽可能避免“使用命名空间标准”。