Implementing Lexicographic Ordering to Find Unique Permutations

Question

I am attempting to implement an algorithm to generate unique permutations in lexicographic order described here. The following is my implementation.

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());
    } 
}

I am sure the algorithm is correct, so what is wrong with my implementation? My function is misses some permutations. The following shows my output compared with std::next_permutation on the input 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
                       ...

Stylistic improvement suggestion: instead of `if (i <= -1)`, write `if (i < 0)`. — , Mar 12 '13 at 05:48

score 2 · Accepted Answer · edited May 23 '17 at 12:11

You're missing step #2 from the linked algorithm

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());
    }
}

Output is:

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 (i.e. 4!) rows, as expected

By the way, you should avoid "using namespace std" as much as possible.

Ironically, you use `using namespace std` it in your solution ;) — idealistikz, Mar 12 '13 at 06:23
@idealistikz only to avoid the complication of reformatting your code so the difference in the versions would be clearer: but I tested it [here](http://ideone.com/7eZREW) without it — Stephen Lin, Mar 12 '13 at 06:25

Implementing Lexicographic Ordering to Find Unique Permutations

1 Answers1