No.31 Next Permutation

这道题主要是全排列问题，输出某一个数字序列的全排列的下一个情况，比如说1,2,3全排列的下一个是1,3,2。

全排列的顺序按字典序排列，比如123的全排列顺序为：

123 132 213 231 312 321

当然最笨的方法还是生成所有全排列然后找。

这道题是有固定的算法的。

以下摘自网上的算法：

算法思想：举例如下

    输入：1 4 6 5 3 2

    step1：从右往左找到第一个破坏升序(非严格)的元素，此例中为4.记下标为 i

    step2: 依然从右往左,找到第一个大于4的元素，此例中5，交换4和5.

    step3：从i+1到最右端，逆置。6 4 3 2 to 2 3 4 6

    so,1 5 2 3 4 6 即为所求。

把全排列的非递归算法滤一遍大概就懂了，因为全排列相当于从最小的数字开始固定在前面的某一位上，因此从右往左找的第一个逆序就是应该替换的位置，比如 1 2 3 4 5这个串，把1固定在最前面，后面全排序2 3 4 5，再把2固定到第二位，后面全排序3 4 5，以此类推，第一个出来的是12345，然后回溯的时候先把4和5颠倒变成12354。发现第一次逆序就说明后面的已经到全排列的最后一个了。

class Solution {public:    void nextPermutation(vector
     
      & nums) {        int pos=-1;        int numLen=nums.size()-1;        for(int i=numLen;i>0;i--){            if(nums[i]>nums[i-1]){                pos=i-1;                break;            }        }        if(pos==-1){            reverse_num(nums,0,numLen);            return;        }        int pos_num=nums[pos];        for(int i=numLen;i>pos;i--){            if(nums[i]>pos_num){                nums[pos]=nums[i];                nums[i]=pos_num;                break;            }        }        reverse_num(nums,pos+1,numLen);    }    void reverse_num(vector
      
       & nums,int begin, int end){        while(begin