How to find Lexicographically previous permutation ? | Function to compute the previous permutation ; Find index of the last element of the string ; Find largest index i such that str [ i - 1 ] > str [ i ] ; if string is sorted in ascending order we 're at the last permutation ; Note - str [ i . . n ] is sorted in ascending order . Find rightmost element 's index  that is less than str[i - 1] ; Swap character at i - 1 with j ; Reverse the substring [ i . . n ] ; Driver code
def prevPermutation ( str ) : NEW_LINE INDENT n = len ( str ) - 1 NEW_LINE i = n NEW_LINE while ( i > 0 and str [ i - 1 ] <= str [ i ] ) : NEW_LINE INDENT i -= 1 NEW_LINE DEDENT if ( i <= 0 ) : NEW_LINE INDENT return False NEW_LINE DEDENT j = i - 1 NEW_LINE while ( j + 1 <= n and str [ j + 1 ] <= str [ i - 1 ] ) : NEW_LINE INDENT j += 1 NEW_LINE DEDENT str = list ( str ) NEW_LINE temp = str [ i - 1 ] NEW_LINE str [ i - 1 ] = str [ j ] NEW_LINE str [ j ] = temp NEW_LINE str = ' ' . join ( str ) NEW_LINE str [ : : - 1 ] NEW_LINE return True , str NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT str = "4321" NEW_LINE b , str = prevPermutation ( str ) NEW_LINE if ( b == True ) : NEW_LINE INDENT print ( " Previous ▁ permutation ▁ is " , str ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " Previous ▁ permutation ▁ doesn ' t ▁ exist " ) NEW_LINE DEDENT DEDENT