Problem
31. Next Permutation
Proof
这个题目有个很绝妙的算法,在这里 有介绍,文章里给出了直觉上的认识,通俗易懂但是不够严格,我这里再证明一下。先把原图搬过来。想偷懒的原文其实可以不看,只看这张图就能知道这算法干了什么。
我们主要关心这个算法的正确性如何。不妨令数组为nums
,把第2步中的pivot记为i
,则数组被分为nums[0:i]
和nums[i+1, n-1]
两部分,算法会确保后者是非递增的。那么这么个操作流程下来,最终生成的排列P P P 到底是不是 第一个 比原排列O O O 大的排列呢,我们用反证法,先假设如下命题为真:
存在一个更优的解——排列Q Q Q ,它比这个排列P P P 更小,且比原排列O O O 更大
首先注意到P和原排列O的nums[0:i-1]
位完全一致,即有P [ 0 : i − 1 ] = Q [ 0 : i − 1 ] P[0:i-1] = Q[0:i-1] P [ 0 : i − 1 ] = Q [ 0 : i − 1 ] ,而Q的大小在他们之间,所以毫无疑问P [ 0 : i − 1 ] = O [ 0 : i − 1 ] = Q [ 0 : i − 1 ] P[0:i-1] = O[0:i-1] = Q[0:i-1] P [ 0 : i − 1 ] = O [ 0 : i − 1 ] = Q [ 0 : i − 1 ] 。于是我们仅需关注[i:n-1]
的部分,那根据Q [ i ] Q[i] Q [ i ] 是否等于O [ i ] O[i] O [ i ] 可以分两种情况讨论。
情况一:Q [ i ] = O [ i ] Q[i]=O[i] Q [ i ] = O [ i ]
这种情况,Q < P Q<P Q < P ,看起来有那么点意思,有更优的感觉了。既然Q [ i ] = O [ i ] Q[i] = O[i] Q [ i ] = O [ i ] ,且Q [ 0 : i − 1 ] = O [ 0 : i − 1 ] Q[0:i-1] = O[0:i-1] Q [ 0 : i − 1 ] = O [ 0 : i − 1 ] ,那么就有Q [ 0 : i ] = O [ 0 : i ] Q[0:i]=O[0:i] Q [ 0 : i ] = O [ 0 : i ] ,即Q [ i + 1 , n − 1 ] Q[i+1, n-1] Q [ i + 1 , n − 1 ] 是由O [ i + 1 , n − 1 ] O[i+1, n-1] O [ i + 1 , n − 1 ] 经过某种变幻得来的。回顾我们计算P的过程,下标范围[ i + 1 , n − 1 ] [i+1, n-1] [ i + 1 , n − 1 ] 是非递增的,也就是说在O O O 中这部分元素已经处于最大排列的状态,不管怎么变幻,得到的结果一定会减小,所以推出Q [ i + 1 , n − 1 ] < O [ i + 1 , n − 1 ] Q[i+1, n-1] < O[i+1, n-1] Q [ i + 1 , n − 1 ] < O [ i + 1 , n − 1 ] ,这意味着Q Q Q 连解都不是,又怎么会是更优解。故此情况下Q Q Q 不是更优解。
情况二:Q [ i ] ≠ O [ i ] Q[i] \neq O[i] Q [ i ] = O [ i ]
既然Q [ i ] ≠ O [ i ] Q[i] \neq O[i] Q [ i ] = O [ i ] ,那么Q [ i : n − 1 ] Q[i:n-1] Q [ i : n − 1 ] 这部分的诞生必然是从[i+1: n-1]
挑了一个数换到了i i i 号位置,然后再对[ i + 1 : n − 1 ] [i+1:n-1] [ i + 1 : n − 1 ] 范围的元素再进行(或不进行,如果非必要的话)某种变幻得来的。注意一下,P [ i ] P[i] P [ i ] 也是这么做出来的,而且换过来的元素是[i+1, n-1]
区间里的元素在满足条件(即大于O [ i ] O[i] O [ i ] )的情况下所能取到的最小值。Q Q Q 虽然比P P P 更优,但是P [ i ] P[i] P [ i ] 的取值已经是可能的最小,Q [ i ] Q[i] Q [ i ] 没得选,只可能与P [ i ] P[i] P [ i ] 相等。至此,结合之前的分析即P [ 0 : i − 1 ] = O [ 0 : i − 1 ] = Q [ 0 : i − 1 ] P[0:i-1] = O[0:i-1] = Q[0:i-1] P [ 0 : i − 1 ] = O [ 0 : i − 1 ] = Q [ 0 : i − 1 ] ,我们就有了Q [ 0 : i ] = P [ 0 : i ] Q[0:i]=P[0:i] Q [ 0 : i ] = P [ 0 : i ] ,即Q [ i + 1 : n − 1 ] Q[i+1:n-1] Q [ i + 1 : n − 1 ] 和P [ i + 1 : n − 1 ] P[i+1:n-1] P [ i + 1 : n − 1 ] 包含的元素是相同的,尽管顺序不确定。再注意到,我们如前所述,数组的[ i + 1 , n − 1 ] [i+1, n-1] [ i + 1 , n − 1 ] 部分是非递增的,P P P 在图中第5步做了逆序后这段元素达到了排列的极限小,也就是说Q Q Q 再怎么优,它所能做的也不过是达到这个极限小而已,此时Q [ i + 1 : n − 1 ] = P [ i + 1 : n − 1 ] Q[i+1:n-1]=P[i+1:n-1] Q [ i + 1 : n − 1 ] = P [ i + 1 : n − 1 ] 。故,Q [ 0 : n − 1 ] = P [ 0 : n − 1 ] Q[0:n-1]=P[0:n-1] Q [ 0 : n − 1 ] = P [ 0 : n − 1 ] ,所以Q Q Q 也不是比P P P 更优的解。
综上所述,原命题不成立,即不存在更优解Q Q Q ,即P已经是最优解。所以这个算法是正确的。
Solution
实现起来非常简单
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 class Solution : def reverse (self, nums, a, b ): i = a j = b while i < j: nums[i], nums[j] = nums[j], nums[i] i += 1 j -= 1 def nextPermutation (self, nums: List [int ] ) -> None : """ Do not return anything, modify nums in-place instead. """ n = len (nums) i = n-1 while i >= 1 : if nums[i] <= nums[i-1 ]: i -= 1 else : break if i == 0 : self.reverse(nums, 0 , n-1 ) return j = n-1 _min = nums[n-1 ] while j >= i: if nums[j] <= nums[i-1 ]: j -= 1 continue else : break nums[i-1 ], nums[j] = nums[j], nums[i-1 ] self.reverse(nums, i, n-1 )