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

tag:array

我们这样来想：

对于一个序列，假设说A[] = {3 4 6 5 3}

先看最后两个数字，5 > 3，所以交换5 3 的话反倒比现在的34653小，不能交换；

再看A[2]和A[3]， A[2] = 6，A[3] = 5，6>5，所以交换6 5 的话也反倒比现在的数字小，不能交换；

再看A[1]和A[2]，A[1] = 4， A[2] = 6，4<6，找到4右侧的比4大且最接近4的数字–5.交换4和5，再把4右侧的数字从小到大排序，得到35346，即为next_permutation.

如果整个序列是从大到小排序的话，则该排列已经是最大的值；将序列再从小到大排序，重新开始一轮循环。

需要指出，在下面的代码中，我为了方便调用sort函数进行vector内部的部分排序，我用了iterator方法而没有用数组下标索引。

class Solution {
public:
    void nextPermutation(vector<int> &num) {
        int size = num.size();
        if(size <= 1){
            return;
        }
        vector<int>::iterator maxV = num.end() - 1;
        for(vector<int>::iterator it = num.end() - 1 ; it >= num.begin(); it--){
            if(*it < *maxV){
                vector<int>::iterator itLarger = maxV;
                for(vector<int>::iterator itp = it; itp != num.end(); itp++){
                    if(*itp > *it && *itp < *itLarger){
                        itLarger = itp;
                    }
                }
                int tmp = *it;
                *it = *itLarger;
                *itLarger = tmp;
                sort((it+1), num.end());
                return;
            }
            else{
                maxV = it;
            }
        }
        //no nexPermutation found, reorder to the smallest permutation
        sort(num.begin(), num.end());
    }
};