How to find Lexicographically previous permutation ? | C ++ program to print all permutations with duplicates allowed using prev_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
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool prevPermutation ( string & str ) { int n = str . length ( ) - 1 ; int i = n ; while ( i > 0 && str [ i - 1 ] <= str [ i ] ) i -- ; if ( i <= 0 ) return false ; int j = i - 1 ; while ( j + 1 <= n && str [ j + 1 ] < str [ i - 1 ] ) j ++ ; swap ( str [ i - 1 ] , str [ j ] ) ; reverse ( str . begin ( ) + i , str . end ( ) ) ; return true ; } int main ( ) { string str = "4321" ; if ( prevPermutation ( str ) ) cout << " Previous ▁ permutation ▁ is ▁ " << str ; else cout << " Previous ▁ permutation ▁ doesn ' t ▁ exist " ; return 0 ; }