【Description】
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

【Idea】

解法： 字典序

以下均源自互联网，具体源出处不明

示例： 1 2 3的全排列如下：

1 2 3 ， 1 3 2 ， 2 1 3 ， 2 3 1 ， 3 1 2 ， 3 2 1

我们这里是通过字典序法找出来的。

那么什么是字典序法呢？

从上面的全排列也可以看出来了，从左往右依次增大，对这就是字典序法。可是如何用算法来实现字典序法全排列呢？

我们再来看一段文字描述：（用字典序法找124653的下一个排列）

如果当前排列是124653，找它的下一个排列的方法是，从这个序列中从右至左找第一个左邻小于右邻的数
如果找不到，则所有排列求解完成，如果找得到则说明排列未完成
本例中将找到46，计4所在的位置为i,找到后不能直接将46位置互换，而又要从右到左到第一个比4大的数
本例找到的数是5，其位置计为j，将i与j所在元素交换125643
然后将i+1至最后一个元素从小到大排序得到125346，这就是124653的下一个排列
下图是用字典序法找1 2 3的全排列（全过程）：

【Solution】

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        if nums == sorted(nums, reverse=True):    # 先排除给定完全逆序排列的数组，改为正序排列
            return nums.reverse()
        length = len(nums)
        i = length - 1
        tag = 0    # 标记数组是否被更改
        while i > 0 and not tag:
            if nums[i-1] < nums[i]:  # 从右向左找到第一个左小于右的数，并记下index
                index = i-1
                j = length-1
                while j > 0 and not tag:  # 从右往左找到第一个大于nums[index]的数，并对两者进行交换
                    if nums[j] > nums[index]:
                        nums[j], nums[index] = nums[index], nums[j]
                        if i < length -1:    # 当目标元素的下标后元素数量大于1时，对其进行正序排列
                            nums[i:] = sorted(nums[i:])
                        tag = 1    
                    j -= 1
            i -= 1