How to generate all permutations of an array in sorted order?

Question

I have an array, and the user can insert a string.

And I have this code:

int main(){
  char anagrama[13];
  cin >> anagrama;
  for(int j = 0; j < strlen(anagrama); j++){
    cout << anagrama[j];
    for(int k = 0; k < strlen(anagrama); k++){
      if(j != k)
        cout << anagrama[k];
    }
    cout << endl;
  }
}

The problem is that I need all permutations of the string in sorted order.

For example if the user write: abc, the output must to be:

abc
acb
bac
bca
cab
cba

and my code doesn't show all permutations, and not sorted

Can you help me?

I need do the implementation without a function already implemented.

I think with a recursive function, but I do not know how.

This is an example: http://www.disfrutalasmatematicas.com/combinatoria/combinaciones-permutaciones-calculadora.html without repetition and sorted

Answer 1

In C++ you can use std::next_permutation to go through permutations one by one. You need to sort the characters alphabetically before calling std::next_permutation for the first time:

cin>>anagrama;
int len = strlen(anagrama);
sort(anagrama, anagrama+len);
do {
    cout << anagrama << endl;
} while (next_permutation(anagrama, anagrama+len));

Here is a demo on ideone.

If you must implement permutations yourself, you could borrow the source code of next_permutation, or choose a simpler way of implementing a permutation algorithm recursively.