LeetCode Next Permutation: Swap and Reverse

Overview

LeetCode Next Permutation: Find the math rule of how to get the next permutation (the smallest larger one) which involves swap and reverse to tackle this problem.

LeetCode Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,31,3,2
3,2,11,2,3
1,1,51,5,1

Solution Analysis: Math Rule,  Swap and Reverse

The solution could be explain by example, consider  7 5 8 6 2 1 –>  next is :  7 6 1 2 5 8, use your maths skills to find out why?

So the approach is: starting from the end, find the longest increasing sequence (8 6 2 1), swap the conflict number (5 here) which disturbs the increasing sequence with the smallest number (6 here) in the increasing sequence which is larger than this conflict number. Reverse the increasing sequence after the conflict number. If we cannot find such conflict number, it means the whole sequence is increasing from right to left. Then the next one is the reversed one of the whole sequence. The following code is accepted by LeetCode OJ to pass this Next Permutation problem:

void nextPermutation(vector<int> &num) {
    int n = num.size();
    if (n < 2) return ;
    int idx = -1;
    for (int i = n - 1; i >= 1 && -1 == idx; --i) if (num[i] > num[i-1]) idx = i - 1;
    if (-1 != idx) {
        for (int i = idx + 1; i < n; ++i) {
            if (num[i] <= num[idx]) {
                swap(num[idx], num[i-1]);
                break;
            }
            if (i == n - 1) swap(num[idx], num[i]);
        }
    }
    reverse(num.begin() + idx + 1, num.end());
}

Summary

LeetCode Next Permutation: Find the math rule of how to get the next permutation (the smallest larger one) which involves swap and reverse to tackle this problem.

Written on June 15, 2013