LeetCode Next Permutation

class Solution {
public:
    void nextPermutation(vector<int> &num) {
        if (num.size() < 2) return;
        int i = num.size() - 2;
        while (i>=0 && (num[i] >= num[i+1])) i--;
        if (i >= 0) {
            int p = num.size() - 1;
            while (p >= 0 && num[p] <= num[i]) p--;
            int t = num[i];
            num[i] = num[p];
            num[p] = t;
        }
        reverse(num.begin() + i + 1, num.end());
    }
};

class Solution {
public:
    void nextPermutation(vector<int> &num) {
        std::next_permutation(num.begin(), num.end());
    }
};

首先C++ STL algorithm里是有next_permutation的，当然这回是自己做题。首先举一些例子

1, 2, 3, 4, 5, 6
1, 2, 3, 4, 6, 5
1, 2, 3, 5, 4, 6
1, 2, 3, 5, 6, 4
1, 2, 3, 6, 4, 5
1, 2, 3, 6, 5, 4
1, 2, 4, 3, 5, 6
1, 2, 4, 3, 6, 5
1, 2, 4, 5, 3, 5

对于一组数字的排列让他们的字典序尽可能的小，一般的想法就是把排序小的数字放在“前面”（类比MSB, Most Signficant Bit），这样的话最小的排列就是一个完全的升序（更确切的是非降序）排列如

1, 2, 3, 4, 5, 6

而一个完全非升序的排列则是最大的一个排列如

6, 5, 4, 3, 2, 1

如果我们发现从末尾开始的某一部分子串已经是非升序排列如

1, 2, 3, 6, 5, 4

中的6,5,4，那么我们可以确定在这个子串所在的位置上仅仅依靠这几个数字已经无法再给出更大的排列，也就是说无法仅靠变换这几个数字的位置来得到next_permutation，于是我们考虑把这个子串中的某个数字与其前面的某个数字交换一下，这样我们又可以给出新的排列了（类比进位，这样处于低位的又可以开始新一轮的循环，只不过这里的数字非常稀缺要借来借去）。因为我们要保证下一个排序尽可能的小，所以我们选择前面子串(1,2,3)中的相当于LSB的最靠后的一个数字，这个例子中是3，同时在后面的子串(6,5,4)选择尽可能小但又比3大（比3大可以保证新产生的排列一定比以前的排列更大）的一个数字，这里是4。交换两者，得到

1, 2, 4, 6, 5, 3

这样处于后部的子串(6,5,3)又可以从最小的排列开始了，因为最小的排列是非降序的，而目前的子串是非升序的（虽然已经交换了一个数字，但依据交换的过程，这个性质还是保持的），所以只要将其翻转一下即可。

1, 2, 4, 3, 5, 6

考虑一下如何降序的给出排列，再考虑如果给出一个排列，怎么判断其实这些排列按字典序从小到大的第几个？

第二轮：

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,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

想了一会还是：

// 16:20
class Solution {
public:
    void nextPermutation(vector<int> &num) {
        int n = num.size();
        if (n <= 1) return;
        
        int q = n - 2;
        while (q >= 0 && num[q] >= num[q+1]) q--;
        if (q < 0) {
            reverse(num.begin(), num.end());
            return;
        }

        int i;
        for (i=n-1; i>q; i--) {
            if (num[i]>num[q]) {
                break;
            }
        }
        swap(num[i], num[q]);
        reverse(num.begin() + q + 1, num.end());
    }
};

可以把两种情况合并一下得到：

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int len = nums.size();
        if (len < 2) {
            return;
        }
        int p = len - 2;
        while (p >=0 && nums[p] >= nums[p+1] ) {
            p--;
        }
        if (p > -1) {
            int q = len - 1;
            while (nums[q] <= nums[p]) {
                q--;
            }
            swap(nums[q], nums[p]);
        }

        reverse(nums.begin() + p + 1, nums.end());
    }
};

最后寻找比某个数大的时候可以使用二分搜索，即STL中的upper_bound来加快速度理论上，不过实际速度差不多

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int len = nums.size();
        int mpos = len - 1;
        while (mpos - 1 >= 0 && nums[mpos-1] >= nums[mpos]) {
            mpos--;
        }
        reverse(nums.begin() + mpos, nums.end());
        if (mpos-1 >= 0) {
            int big = upper_bound(nums.begin() + mpos, nums.end(), nums[mpos - 1]) - nums.begin();
            swap(nums[mpos - 1], nums[big]);
        }
    }
};