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.

http://www.lintcode.com/en/problem/next-permutation/

Discussion

记住算法coding不难。

1. 从右向左应该是升序的，找到第一个破坏升序的number A
2. 从右向左找到第一个比A大的number B
3. 交换AB
4. 从交换前的A位置后一个位置一直到序列最后的位置，反转

注意：若没有找到A，也就是整个从右到左都是升序，比如4 3 2 1，那么就整个属猪反转变成1 2 3 4. 用一个实例总会好理解并记住这个算法。比如1 4 3 2 以后怎么得到2 1 3 4呢？找到1， 找到2， 交换1 2， 反转1后面的三个数字的顺序，哦了。

Solution

class Solution {
public:
    /**
     * @param nums: An array of integers
     * @return: An array of integers that's next permuation
     */
    vector<int> nextPermutation(vector<int> &nums) {
        // write your code here
        vector<int> result;
        int n = nums.size();
        if(n == 0) return result;
        int partitionNumIdx = n-1;
        bool swap = false;
        for(int i = n-2; i>=0; i--) {
            if(nums[i] < nums[i+1]) {
                partitionNumIdx = i;
                swap = true;
                break;
            }

        }
        int changeNumIdx = 0;
        if(swap == false) {
            sort(nums.begin(), nums.end());
            return nums;
        }
        for(int i = n-1; i>=0; i--) {
            if(nums[i] > nums[partitionNumIdx]) {
                changeNumIdx = i;
                break;
            }
        }
        int tmp = nums[changeNumIdx];
        nums[changeNumIdx] = nums[partitionNumIdx];
        nums[partitionNumIdx] = tmp;
        sort(nums.begin()+partitionNumIdx+1, nums.end());
        return nums;
    }
};

更简洁的一个版本。

class Solution {
public:
    /**
     * @param nums: An array of integers
     * @return: An array of integers that's next permuation
     */
    vector<int> nextPermutation(vector<int> &nums) {
        // write your code here
        if(nums.size() <=1) return nums;
        int n = nums.size();
        int breakid = -1;
        for(int i=n-2; i>=0; i--) {
            if(nums[i] < nums[i+1]) {
                breakid = i;
                break;
            }
        }
        if(breakid == -1) {
            reverse(nums.begin(), nums.end());
            return nums;
        }
        int switchid = -1;
        for(int i=n-1; i>breakid; i--) {
            if(nums[i] > nums[breakid]) {
                switchid = i;
                break;
            }
        }
        swap(nums[switchid], nums[breakid]);
        reverse(nums.begin()+breakid+1, nums.end());
        return nums;
    }
};

Reference

http://fisherlei.blogspot.com/2012/12/leetcode-next-permutation.html