Next permutation

这是一道排列的问题。在编程里，为了完成排列，基本上是由一个升序的数组，然后通过N次排列，生成N个中间排列结果，直到排列为倒序的数组，这样就会有N+2个排列方式。先看题目：

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 and use only constant 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

下面直接记录下排列的思路：

1. 从最后一个元素向前查找元素，直到查找到某个元素a[n]大于a[n-1]，也就是查找到第一个降序的元素
2. 从最后一个元素向前查找元素，查到第一个大于a[n-1]的元素，并将其和a[n-1]进行替换
3. 将a[n]和其后的元素作一次翻转操作

下面是代码：

static void nextPermutation(vector<int>& nums) {
    for (int i = nums.size() - 2; i >= 0; i--) {
        if (nums[i] < nums[i + 1]) {
            for (int j = nums.size() - 1; j >= i + 1; j--) {
                if (nums[j] > nums[i]) {
                    std::swap(nums[j], nums[i]);
                    break;
                }
            }
            std::reverse(nums.begin() + i + 1, nums.end());
            return;
        }
    }
    return std::reverse(nums.begin(), nums.end());
}