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
def reverse ( str , l , h ) : NEW_LINE INDENT while ( l < h ) : NEW_LINE INDENT str [ l ] , str [ h ] = str [ h ] , str [ l ] NEW_LINE l += 1 NEW_LINE h -= 1 NEW_LINE DEDENT return str NEW_LINE DEDENT def findCeil ( str , c , k , n ) : NEW_LINE INDENT ans = - 1 NEW_LINE val = c NEW_LINE for i in range ( k , n + 1 ) : NEW_LINE INDENT if str [ i ] > c and str [ i ] < val : NEW_LINE INDENT val = str [ i ] NEW_LINE ans = i NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT def sortedPermutations ( str ) : NEW_LINE INDENT size = len ( str ) NEW_LINE str = ' ' . join ( sorted ( str ) ) NEW_LINE isFinished = False NEW_LINE while ( not isFinished ) : NEW_LINE INDENT print ( str ) NEW_LINE for i in range ( size - 2 , - 1 , - 1 ) : NEW_LINE INDENT if ( str [ i ] < str [ i + 1 ] ) : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT if ( i == - 1 ) : NEW_LINE INDENT isFinished = True NEW_LINE DEDENT else : NEW_LINE INDENT ceilIndex = findCeil ( str , str [ i ] , i + 1 , size - 1 ) NEW_LINE str [ i ] , str [ ceilIndex ] = str [ ceilIndex ] , str [ i ] NEW_LINE str = reverse ( str , i + 1 , size - 1 ) NEW_LINE DEDENT DEDENT DEDENT