Nov 7, 2018

How to find the next higher permutation

1. Take the current permutation and find the rightmost character in it, which is smaller than its next character. Let us call this character as ‘Alpha’.

2. Now find the ceiling of ‘Alpha’ which is the smallest character on the right of ‘Alpha’, which is greater than ‘Alpha’. Let us call it ‘Beta’.

3. Swap the two characters found in above 2 steps.

4. Sort the sub-string (in non-decreasing order) after the original index of ‘Alpha’.

For example for the string “ABCDE”. Let current permutation be “DCEBA”. The next permutation in sorted order should be “DEABC”. Let us go through above steps to find next higher permutation. The ‘Alpha’ will be ‘C’. The ‘Beta’ will be ‘E’. After swapping these two, we get “DECBA”. The final step is to sort the sub-string after the character original index of ‘Alpha’. The sub-string is "CBA", sort it into "ABC", Finally, we get “DEABC”.

Because the sub-string we get after swapping "Alpha" and "Beta" is always sorted in non-increasing order ( in former example it is "CBA"), we can simply reverse the sub-string to sort it in non-decreasing order ( "CBA" -> "ABC").

There could be duplicate permutation when characters are repeated. We can avoid it by keeping track of the previous permutation. If the current permutation is the same as previous, we can choose to ignore it if that is what we need.