本题目在凌应标老师的《算法设计与分析》第八次作业中出现，可供参考。
题目描述：
实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须原地修改，只允许使用额外常数空间。
以下是一些例子，输入位于左侧列，其相应输出位于右侧列。1,2,3 → 1,3,23,2,1 → 1,2,31,1,5 → 1,5,1
要完成的函数：
void nextPermutation(vector<int>& nums)
说明：
1、这道题给定一个vector，里面装着各种数字，比如123这样子，要求按照字典序输出当前排列的下一种排列，比如123的下一种字典序排列就是132。
如果当前已经不存在更大的下一种排序，比如321，已经到达最大了，那么输出123，这种最小的字典序排列。
除此之外，只允许原地修改，使用额外常数级空间。
2、这道题挺有意思的，如果要求输出所有的排列情况，并且按照字典序排列，存储在vector中返回，你会怎么做？
笔者觉得也许可以参考leetcode-17-电话号码的字母组合这种思路来做。
回到当前这道题，我们写几个排列来看下情况，如下：
1234的下一个排列是1243，从后面找起，如果倒数第二个比倒数第一个小，那么交换两个的数值，结束。
1243的下一个排列是1324，从后面找起，倒数第二个不会比倒数第一个小，所以只能继续往前走，倒数第三个比倒数第二个小，所以我们只需要交换从倒数第三个开始的vector元素。
1324的下一个排列是1342，规则一样，从后面找起，倒数第二个比倒数第一个小，交换两个的数值，结束。
1342的下一个排列是1423，从后面找起，倒数第二个不会比倒数第一个小，所以只能继续往前走，倒数第三个比倒数第二个小，所以我们只需要交换从倒数第三个开始的vector元素。
……
1432的下一个排列是2134，从后面找起，发现只有第一位小于第二位，所以我们要交换整个vector中的元素。
通过上述举例，我们可以发现，如果前面一个的数值小于后面一个，那么我们就要交换从前面一个到vector最后面的所有元素。而如果不满足这个条件，那么继续往前走。
如果走到第一位了，发现还是不满足，那么说明当前排列已经是字典序最大的排列了，我们只需要两两交换一下，便可以变成字典序最小的排列。
那我们要怎样交换从前面一个到vector最后面的所有元素？
举个例子，2431的下一个排列，是3124。
我们往前走到第一位，才找到前一个元素2小于后一个元素4的情况，此时，我们继续从后面找起，找到大于前一个元素的第一个元素3，因为431这种排列，决定了从后面找起的第一个大于前一个元素的元素3，是大于前一个元素2的最小元素。
交换他们的数值，这时候变成3421。
接着从4开始，头跟尾两两不断交换，也就是我们最终要的结果，3124。
附上代码，如下：
void nextPermutation(vector<int>& nums)
{
int s1=nums.size()-1,s2=s1-1,i;//s1表示最后一位，s2表示我们最开始从倒数第二位开始找起
while(s2>=0)//一直找，找到前一个元素小于后一个元素的这种情况
{
if(nums[s2]<nums[s2+1])
break;
s2--;
}
if(s2==-1)//如果全程没找着，s2已经是-1了，那么说明当前是字典序最大的排列
{
for(int i=0;i<=s1/2;i++)//头跟尾两两不断地交换
swap(nums[i],nums[s1-i]);
}
else//如果找着了，nums[s2]这时候要跟后面大于nums[s2]的最小元素交换数值
{
i=s1;
while(i>s2)//找到大于nums[s2]的最小元素
{
if(nums[i]>nums[s2])
break;
i--;
}
swap(nums[s2],nums[i]);//两两交换数值
for(i=s2+1;i<=(s1+s2+1)/2;i++)//从s2+1这个位置开始，头跟尾两两不断地交换
swap(nums[i],nums[s1+s2+1-i]);
}
}
这道题有意思就有意思在，你发现你要再往前找一位来交换的时候，比如2431，你必须找到2，2是第一个小于后面元素4的元素，这时候你会发现2后面的排列刚好是从大到小的排列，是一个降序排列。
因为是降序排列，所以省去我们很多功夫，比如找到大于2的最小元素，只需要从后面找起，第一个大于2的3就是了。
再比如交换完2和3这两个数值，我们得到了3421，接下来我们从4开始，后面的元素（包括4本身），还是一个降序排列，继续头跟尾两两交换就可以了。
笔者最开始还想得挺复杂，比如什么逐一比较，找到大于2的最小元素；什么4之后的元素通过冒泡排序来调整顺序。但都不需要。
上述代码实测8ms，beats 100.00% of cpp submissions。
