Print all permutations in sorted ( lexicographic ) order |  ; An optimized version that uses reverse instead of sort for finding the next permutation A utility function to reverse a string str [ l . . h ] ;  ;  ; Print all permutations of str in sorted order ; Get size of string ; Sort the string in increasing order ; Print permutations one by one ; print this permutation ; Find the rightmost character which is smaller than its next character . Let us call it ' first ▁ char ' ; If there is no such character , all are sorted in decreasing order , means we just printed the last permutation and we are done . ; Find the ceil of ' first ▁ char ' in right of first character . Ceil of a character is the smallest character greater than it ; Swap first and second characters ; reverse the string on right of ' first ▁ char '
#include <bits/stdc++.h> NEW_LINE using namespace std ; void reverse ( char str [ ] , int l , int h ) { while ( l < h ) { swap ( & str [ l ] , & str [ h ] ) ; l ++ ; h -- ; } } void swap ( char * a , char * b ) { char t = * a ; * a = * b ; * b = t ; } int compare ( const void * a , const void * b ) { return ( * ( char * ) a - * ( char * ) b ) ; } int findCeil ( char str [ ] , char first , int l , int h ) { int ceilIndex = l ; for ( int i = l + 1 ; i <= h ; i ++ ) if ( str [ i ] > first && str [ i ] < str [ ceilIndex ] ) ceilIndex = i ; return ceilIndex ; } void sortedPermutations ( char str [ ] ) { int size = strlen ( str ) ; qsort ( str , size , sizeof ( str [ 0 ] ) , compare ) ; bool isFinished = false ; while ( ! isFinished ) { cout << str << endl ; int i ; for ( i = size - 2 ; i >= 0 ; -- i ) if ( str [ i ] < str [ i + 1 ] ) break ; if ( i == -1 ) isFinished = true ; else { int ceilIndex = findCeil ( str , str [ i ] , i + 1 , size - 1 ) ; swap ( & str [ i ] , & str [ ceilIndex ] ) ; reverse ( str , i + 1 , size - 1 ) ; } } }