Next Permutation

Lexicographical order basically means dictionary order. A sequence is said to be lexicographically larger than another sequence if it’ll appear later in a dictionary. Eg, the following list is lexicographically sorted –

ABC, ACB, BAC, BCA, CAB, CBA


 Now, consider a sequence

int a[] = {1,5,3,8,7,5,4,2};

By some trial and error, we can conclude that lexicographically the next sequence is {1,5,4,2,3,5,7,8}. Now how we go about generating it algorithmically?

Intuitively, to “increase” the sequence as little as possible, we need to take the same approach as when counting up numbers. We need to modify the rightmost elements(analogous to unit digits) and disturb the letters on the left as little as possible. For example, if we swap the first two elements we get {2,5,3,8,7,5,4,1}, which is much larger lexicographically when compared to what we get if we swap the two rightmost elements {1,5,3,8,7,5,2,4}. Now the question is, which numbers do we swap and why?

Let’s identify the longest weakly increasing suffix (each element larger than or equal to the elements on their right). In the given scenario, such sequence is {8,7,5,4,2}. The critical observation here is to note that this sequence is already lexicographically sorted in decreasing order. It is another way to saying that it is not possible to make a number larger than 87542 using the digits 2,4,5,7,8. Note that to increase the given sequence as little as possible, we need to increase the prefix (everything apart from the weakly increasing sub-sequence) and the suffix as little as possible.

Let us consider the element immediately to the left of this sub sequence. In our case, it is 3. The second critical observation is to note that this element has to be by definition lesser than the leftmost element of the weakly increasing sub-sequence. We can therefore conclude that this element is lesser than atleast one element in the sub-sequence {8,7,5,4,2}. To minimize the prefix, we swap this element with the smallest element in the suffix that is larger than 3.

Old sequence

New sequence

Finally, to minimize the suffix, we sort it in increasing order, to get {1,5,4,2,3,5,7,8}. Note that we just need to reverse it to sort it in increasing order.

And there we have it! The next lexicographic permutation is {1,5,4,2,3,5,7,8}. Once again, the steps are

1.  Identify the longest weakly increasing suffix.
2.  If the suffix is the entire sequence, then the sequence is already reverse sorted lexicographically and it is not possible to generate a larger sequence.
3.  Else, identify the element immediately to the left of the suffix.
4.  Swap this element with the smallest element in the suffix larger than it to minimize the prefix.
5.  Sort the new suffix in increasing order to minimize the suffix.
6.  Done!

/**
  2   5   6(i)   8(j)   3   2

**/
class Solution {
    public void nextPermutation(int[] nums) {
        
        if(nums == null || nums.length == 0){
            return;
        }
        int i = nums.length - 2;
        while( i >= 0 && nums[i] >= nums[i+1]){
            i--;
        }
        if( i >= 0){
            int j = nums.length - 1;
            while( j >= i && nums[j] <= nums[i]){
                j--;
            }
            swap(nums, i, j);
        }
        i += 1;
        int j = nums.length - 1;
        while( i < j){
            swap(nums, i++, j--);
        }
    }
    
    private void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i]  = nums[j];
        nums[j]  = temp;
    }
}

Categories: Array

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s