Find all lexicographically next permutations of a string sorted in ascending order

Given a string sorted in ascending order, find all lexicographically next 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,


Lexicographically next permutation of the string ABCD is ABDC
Lexicographically next permutation of the string ABDC is ACBD
Lexicographically next permutation of the string ACBD is ACDB

 


 

Simple solution would be to use std::next_permutation that generates the next greater lexicographic permutation of a string. If the function can determine the next higher permutation, it rearranges the elements as such and returns true. If that was not possible (because it is already at the largest possible permutation), it rearranges the elements according to the first permutation (sorted in ascending order) and returns false.

 
C++ implementation –
 

Download   Run Code

Output:

ABCD ABDC ACBD ACDB ADBC ADCB BACD BADC BCAD BCDA BDAC BDCA
CABD CADB CBAD CBDA CDAB CDBA DABC DACB DBAC DBCA DCAB DCBA

 

We can also implement our own next_permutation function. The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.

  • Find largest index i such that str[i-1] is less than str[i].
  • Return false if i is first index of the string, meaning that we are already at highest possible permutation i.e. string is sorted in descending order. If i is not the first index of the string, then the substring str[i..n) is sorted in descending order i.e.

    str[i-1] < str[i] >= str[i+1] >= str[i+2] >= … >= str[n-1].

  • Find a highest index j to the right of index i such that str[j] is greater than str[i–1] and swap characters at index i-1 with index j.
  • Reverse the substring str[i..n) and return true

 
C++ implementation –
 

Download   Run Code

Output:

ABCD ABDC ACBD ACDB ADBC ADCB BACD BADC BCAD BCDA BDAC BDCA
CABD CADB CBAD CBDA CDAB CDBA DABC DACB DBAC DBCA DCAB DCBA

 

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 will not print duplicate permutations.
 
 

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 🙂
 





Sort by:   newest | oldest | most voted
AllergicToBitches
AllergicToBitches
wpDiscuz