Print All Permutations in Sorted Lexicographic Order in C++

In this problem, we are given a string of length n and we have to print all permutations of the characters of the string in sorted order.

Let’s take an example to understand the problem :

Input: ‘XYZ’

Output: XYZ, XZY, YXZ, YZX, ZXY, ZYX.

Here we have to print all permutations in lexicographical order (alphabetically increasing order).

To solve this problem, we have to first sort the array in alphabetically increasing order, the sorted array is the first element of the permutation. And then generate the next higher order permutation of the string.

The below code will make the solution more clear to you :

Example

 Live Demo

#include<iostream>
#include<string.h>
using namespace std;
int compare(const void *a, const void * b){
   return ( *(char *)a - *(char *)b );
}
void swap(char* a, char* b) {
   char t = *a;
   *a = *b;
   *b = t;
}
int finduBound(char str[], char first, int l, int h) {
   int ubound = l;
   for (int i = l+1; i <= h; i++)
      if (str[i] > first && str[i] < str[ubound])
   ubound = i;
   return ubound;
}
void generatePermutaion ( char str[] ) {
   int size = strlen(str);
   qsort( str, size, sizeof( str[0] ), compare );
   bool isFinished = false;
   while ( ! isFinished ) {
      cout<<str<<"\t";
      int i;
      for ( i = size - 2; i >= 0; --i )
         if (str[i] < str[i+1])
            break;
         if ( i == -1 )
            isFinished = true;
      else {
         int ubound = finduBound( str, str[i], i + 1, size - 1 );
         swap( &str[i], &str[ubound] );
         qsort( str + i + 1, size - i - 1, sizeof(str[0]), compare );
      }
   }
}
int main() {
   char str[] = "NOPQ";
   cout<<"Permutation in Sorted order :\n";
   generatePermutaion(str);
   return 0;
}

Output

Permutation in Sorted order :
NOPQ NOQP NPOQ NPQO NQOP NQPO
ONPQ ONQP OPNQ OPQN OQNP
OQPN PNOQ PNQO PONQ POQN
PQNO PQON QNOP QNPO QONP
QOPN QPNO QPON