Problem

31. Next Permutation

Proof

这个题目有个很绝妙的算法,在这里有介绍,文章里给出了直觉上的认识,通俗易懂但是不够严格,我这里再证明一下。先把原图搬过来。想偷懒的原文其实可以不看,只看这张图就能知道这算法干了什么。

我们主要关心这个算法的正确性如何。不妨令数组为nums,把第2步中的pivot记为i,则数组被分为nums[0:i]nums[i+1, n-1]两部分,算法会确保后者是非递增的。那么这么个操作流程下来,最终生成的排列PP到底是不是 第一个 比原排列OO大的排列呢,我们用反证法,先假设如下命题为真:

存在一个更优的解——排列QQ,它比这个排列PP更小,且比原排列OO更大

首先注意到P和原排列O的nums[0:i-1]位完全一致,即有P[0:i1]=Q[0:i1]P[0:i-1] = Q[0:i-1],而Q的大小在他们之间,所以毫无疑问P[0:i1]=O[0:i1]=Q[0:i1]P[0:i-1] = O[0:i-1] = Q[0:i-1]。于是我们仅需关注[i:n-1]的部分,那根据Q[i]Q[i]是否等于O[i]O[i]可以分两种情况讨论。

情况一:Q[i]=O[i]Q[i]=O[i]

这种情况,Q<PQ<P,看起来有那么点意思,有更优的感觉了。既然Q[i]=O[i]Q[i] = O[i],且Q[0:i1]=O[0:i1]Q[0:i-1] = O[0:i-1],那么就有Q[0:i]=O[0:i]Q[0:i]=O[0:i],即Q[i+1,n1]Q[i+1, n-1]是由O[i+1,n1]O[i+1, n-1]经过某种变幻得来的。回顾我们计算P的过程,下标范围[i+1,n1][i+1, n-1]是非递增的,也就是说在OO中这部分元素已经处于最大排列的状态,不管怎么变幻,得到的结果一定会减小,所以推出Q[i+1,n1]<O[i+1,n1]Q[i+1, n-1] < O[i+1, n-1],这意味着QQ连解都不是,又怎么会是更优解。故此情况下QQ不是更优解。

情况二:Q[i]O[i]Q[i] \neq O[i]

既然Q[i]O[i]Q[i] \neq O[i],那么Q[i:n1]Q[i:n-1]这部分的诞生必然是从[i+1: n-1]挑了一个数换到了ii号位置,然后再对[i+1:n1][i+1:n-1]范围的元素再进行(或不进行,如果非必要的话)某种变幻得来的。注意一下,P[i]P[i]也是这么做出来的,而且换过来的元素是[i+1, n-1]区间里的元素在满足条件(即大于O[i]O[i])的情况下所能取到的最小值。QQ虽然比PP更优,但是P[i]P[i]的取值已经是可能的最小,Q[i]Q[i]没得选,只可能与P[i]P[i]相等。至此,结合之前的分析即P[0:i1]=O[0:i1]=Q[0:i1]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[i+1:n1]Q[i+1:n-1]P[i+1:n1]P[i+1:n-1]包含的元素是相同的,尽管顺序不确定。再注意到,我们如前所述,数组的[i+1,n1][i+1, n-1]部分是非递增的,PP在图中第5步做了逆序后这段元素达到了排列的极限小,也就是说QQ再怎么优,它所能做的也不过是达到这个极限小而已,此时Q[i+1:n1]=P[i+1:n1]Q[i+1:n-1]=P[i+1:n-1]。故,Q[0:n1]=P[0:n1]Q[0:n-1]=P[0:n-1],所以QQ也不是比PP更优的解。

综上所述,原命题不成立,即不存在更优解QQ,即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)