Next Permutation

LeetCode #31

EPI check to see why this algorithm.

Description:

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.

Example:

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

Idea:

1. from right to left, find the first digit that is not increasing. (equal does not count), locate this index, ind1.
2. from right to ind1, find the first digit that is larger than nums[ind1], locate this index, ind2.
3. swap(nums[ind1], nums[ind2]).
4. reverse nums from ind1+1 to last element.

Code:

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        if(nums.size()<=1) return;

        int N=nums.size();
        int ind1=-1;
        for(int i=N-2; i>=0; --i){
            if(nums[i]<nums[i+1]){
                ind1=i;
                break;
            }
        }
        // if not find, mean it's the last sequence, then return the first sequence
        if(ind1 == -1){
            reverse(nums, 0, N-1);
            return;
        }

        int ind2=N-1;
        for(int i=N-1; i>ind1; --i){
            if(nums[i]>nums[ind1]){
                ind2=i;
                break;
            }
        }

        swap(nums[ind1], nums[ind2]);
        reverse(nums, ind1+1, N-1);
    }

    void reverse(vector<int>& nums, int first, int last){
        while(first<last){
            swap(nums[first], nums[last]);
            first++;
            last--;
        }
    }
};