31. Next Permutation

1. Next Permutation https://yq.aliyun.com/articles/863 思路 假设有一个数： abcd...hi...wxyz 从i到z递减，且h小于i。 我们的任务是找到一个排列比它大，且尽可能小。 那么如果要找一个比它大的数，这个数的第一位不同必须在h上。下面用反证法证明：
2. 如果该位在h以前，也就是abc...一直到h之前，那么这个数一定比 在h位上不同的数要大。
3. 如果该位在h之后，也就是i...wxyz，那就说明i位之前的数都是一样的，没有交换过。而i...wxzy是递减的，在局部上本来就是数最大的排列，任何交换都无法使它更大。所以也不可能在h之后。

所以该位在h上。那么h要与谁交换呢？这个数肯定要比h大，但又要尽可能小。所以就在h右侧寻找比它大又尽可能小的数。将他们交换。然后剩下的数就从左到右，从小到大排序，就可以得到结果了。