Реализация лексикографического заказа для поиска уникальных перестановок

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

Я уверен, что алгоритм верен, и что не так с моей реализацией? Моя функция пропускает некоторые перестановки. Ниже показан мой результат по сравнению с 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 строки, как и ожидалось

По путь, вы должны avoid "using namespace std" по возможности.