std::prev_permutation | Overview & Implementation in C++

In this post, we will discuss about std::prev_permutation which can be used to find the lexicographically smaller permutations of a string.


 

The lexicographic or lexicographical order (aka 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 previous permutation in lexicographic order for the string 213 is 132.

 
STL provides std::prev_permutation which returns the previous permutation in lexicographic order by in-place rearranging the specified object as a lexicographically smaller permutation. The function returns true if previous permutation exists, else it returns false to indicate that the object is already at the highest possible permutation and reset the range according to the last permutation.

std::prev_permutation generates the previous permutation in mere linear time and also handle repeated characters to generate the distinct permutations. Below C++ program demonstrates its usage:

 

Download   Run Code

Output:

231 213 132 123

 

We can also implement our own prev_permutation method. The following in-place algorithm lexicographically generates the previous permutation after a given permutation.

  • Find largest index i such that s[i-1] > s[i].
     
  • If i is the first index of the string, the permutation is the first permutation else s[i..n-1] is sorted in natural order i.e. s[i-1] > s[i] <= s[i+1] <= s[i+2] <= ... <= s[n-1].
     
  • Find a highest index j such that j >= i and s[j] < s[i-1] and swap characters at index i-1 with index j.
     
  • Reverse the substring s[i..n-1] and return true

 

Download   Run Code

Output:

231 213 132 123

 

Since there are n! permutations and each permutations takes linear time, the time complexity of above solution is O(n.n!). Here n is the length of the given string. The worst case happens when the string contains all distinct elements and the best case happens when the string contains all repeated characters.
 

 
Also See: std::next_permutation

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz