Given a string sorted in descending order, find all lexicographically previous permutations of it.
The lexicographic or lexicographical order (also known as lexical order, dictionary order, alphabetical order) means that the words are arranged in a similar fashion as they are presumed to appear in a dictionary. For example, the lexicographically previous permutation of the string DCBA is DCAB, for string DCAB is DBCA, and for string DBCA is DBAC.
Simple solution would be to use std::prev_permutation that generates the next smaller lexicographic permutation of a string. If the function can determine the previous permutation, it rearranges the characters as such and returns true. If that was not possible (because it is already at the lowest possible permutation), it rearranges the characters according to the last permutation (sorted in descending order) and returns false.
// Function to find all lexicographically previous permutations of a
// string sorted in descending order using std::prev_permutation
We can also implement our own prev_permutation function. The following algorithm generates the previous permutation lexicographically after a given permutation. It changes the given permutation in-place.
Find largest index i such that str[i] is less than str[i-1].
Return false if i is first index of the string, meaning that we are already at lowest possible permutation i.e. string is sorted in ascending order. If i is not the first index of the string, substring str[i..n) is sorted in ascending order i.e.
The worst case time complexity of above solutions is O(n.n!) as there are n! permutations for a string of length n and each permutations takes O(n) time. Worst case happens when the string contains all distinct elements.
Note that above solution can handle strings containing repeated characters and do not print duplicate permutations.