数学证明 LeetCode 31. Next Permutation

Problem

31. Next Permutation

Proof

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

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

存在一个更优的解——排列$Q$，它比这个排列$P$更小，且比原排列$O$更大

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

情况一：$Q[i]=O[i]$

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

情况二：$Q[i] \neq O[i]$

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

综上所述，原命题不成立，即不存在更优解$Q$，即P已经是最优解。所以这个算法是正确的。

Solution

实现起来非常简单

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)