31. 下一个排列

题目
实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须原地修改，只允许使用额外常数空间。

字典序

字典序，就是将元素按照字典的顺序（a-z, 1-9）进行排列。以字典的顺序作为比较的依据，可以比较出两个串的大小。比如 “12345” < “12354”<“12435”<“12453”， 就是按每个数字位逐个比较的结果。字典序法要求这一个与下一个有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。
12354 与 12435
1 == 1
2 == 2
3 < 4

生成下一个排列

1. 从右向左，找到第一个违反升序的，叫他‘partitionnumber’。
2. 从右向左，找到第一个比刚才那个数大的数，叫他‘changenumber’。
3. 交换着两个数，然后把在partitionnumber右边的数顺序反过来。

算法正确性证明

• 证明它可以生成所有的排列只需要证明生成的下一个排序恰好比当前排列大的一个序列即可。
• 对于任意j，作为从右端开始第一个小于右边数字的数，可以得到序列Pj+1，…Pn是降序排列；
• 选择其中大于Pj的最小的数字Pk，与其交换，然后再对后面排序得到序列P1，…Pj-1Pk…Pn，恰好比P1…Pj-1Pj…Pn大一点的下一个排列，因此算法可以生成全排列。
  

例1
2 4 3 1
3 1 是倒序排列，4 3 1 是倒序排列，2 4 3 1不是倒序排列，且2 4 3 1是2分支中的最后一个排列，因此下一个排列 肯定要换成一个比2更大的数的分支中的第一个排列，即换成 4 3 1中大于2的数中的最小的数 3，变为 3 4 2 1，此时 4 2 1为倒序，也就是说 3 4 2 1是3分支中的最后一个排列，第一个排列即是 顺序排列 4 2 1，最终为 3 1 2 4

例2
3 2 4 1
3分支下的2分支下的最后一个排列 变为 3分支下的4分支下的第一个排列
3 4 1 2

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        
        n = len(nums)
        
        partition = n
        for i in range(n-1, 0, -1):
            
            if nums[i] > nums[i - 1]:
                partition = i - 1
                break
                
        if partition == n:
            nums.reverse()
            return
            
        for j in range(n-1, partition, -1):
            
            if nums[j] > nums[partition]:
                nums[partition], nums[j] = nums[j], nums[partition]
                break
        
        nums[partition+1:n] = nums[partition+1:n][::-1]