下一个排列问题

引言

有时候我们会想要生成一个序列的「下一个排列」或者是「上一个排列」，你会怎么做呢？如果你对 C++ 很熟悉的话，不难想到可以用 next_permutation¹ 和 prev_permutation²。但是 Python 并没有提供类似的 API。因此今天要探讨的就是如何用 Python 实现这 2 个 API，又因为「上一个排列」和「下一个排列」的方法其实大同小异，因此让我们聚焦其中的「下一个排列」问题

算法流程

也许会让你感到意外的是，「下一个排列」问题在 14 世纪的时候就有人想出解决办法来了³，假设现在给定一个序列 a，下面是具体的算法步骤

1. 找到最大的索引 k 使得 a[k] < a[k + 1]，如果不存在这样的索引的话，那么说明当前的序列已经是最后一个排列了
2. 找到最大的索引 l，l > k 而且 a[k] < a[l]
3. 交换 a[k], a[l] 的值
4. 翻转从 a[k + 1] 开始的部分

这样你就得到了「下一个排列」，但为什么这个算法是正确的？接下来我们逐步拆解一下这些步骤背后的原理

算法的理解

试问一个问题，在不知道这个算法之前，你会如何解决「下一个排列」问题？如果你对回溯算法很熟悉的话，应该不难想到我们可以干脆从第一个排列开始暴力枚举，逐个对比就容易定位到当前序列的下一个排列了。当然这个算法的复杂度太高，达到了 $O(N!)$。因此我们可以尝试优化一下，这就带来了第一个问题

Q1 - 用回溯算法生成当前序列的「下一个排列」的时候有什么特点？

我们可以按顺序打出 [1, 2, 3, 4] 的所有排列并尝试找一下规律

[[1, 2, 3, 4],
 [1, 2, 4, 3],
 [1, 3, 2, 4],
 [1, 3, 4, 2],
 [1, 4, 2, 3],
 [1, 4, 3, 2],
 [2, 1, 3, 4],
 ...  # omit
 [4, 3, 2, 1]]

就看其中一个例子好了，[1, 4, 3, 2] 为什么下一个排列是 [2, 1, 3, 4]？你能否发现什么规律？更确切地说，为什么第一位从 1 变成了 2？[1, 4, 3, 2] 这个序列有什么特点？可以看到末尾的 4, 3, 2 是最长非递增后缀的，那么这个规律适用任何情况吗？不妨再看另外一个例子，[1, 2, 4, 3] -> [1, 3, 2, 4]，你会发现，同样的，我们仍然可以找到一个最长非递增后缀 [4, 3]，同时第二位的 2 变成了 3，把这些并排放在一起可能会更直观些：

[1, 4, 3, 2]
    ^
    # non-increasing suffix
[2, 1, 3, 4]
 ^
 # change this

[1, 2, 4, 3]
       ^
       # non-increasing suffix
[1, 3, 2, 4]
    ^
    # change this

所以结论似乎是——找到序列末尾的最长非递增后缀的开始位置 j，要生成下一个序列的话需要调大 j - 1 的位置的值。这恰恰是前面算法流程的第一步做的事情。如果从上面的观察导出这个结论无法说服你，那么可以从回溯的代码角度入手，什么时候会修改 j - 1 的值？答案是当我们已经枚举完 a[j:] 部分的所有排列的时候，那么这个时候 a[j:] 有什么特点？特点是，从 a[j:] 会是非递增的，因为我们回溯的时候是按照字典序从小到大枚举

indices: 0, 1, 2, ..., j - 1, j, ..., n - 1
                   # a[j - 1] < a[j]

A1 - 在生成下一个排列的时候，我们总是会调大末尾的最长非递增后缀的左边一个位置的元素

为了后续讨论方便，我们称前面找到的最长非递增后缀左边的位置为 pivot（也就是前面的 j - 1）。那么现在就引出了第二个问题

Q2 - a[pivot] 的值要怎么改变？

因为要求解的是下一个排列，因此我们希望 a[pivot] 要增加，而且不要增加太多，应该增加“一点点”就好，那么什么是这个“一点点”？仍然从回溯的角度理解，我们会按照字典序从小到大枚举，因此 a[pivot] 应该要变成比它更大的下一个元素，那么这个下一个更大的元素去哪里找？答案是在 a[pivot + 1:] 里面找，换言之，我们要去 a[pivot + 1:] 里面找比 a[pivot] 大而且尽量小的元素

别忘了 a[pivot + 1:] 的特点：它是非递增的，因此我们可以从右到左检查 a[pivot + 1:] 这个部分的元素的值，找到第一个比 a[pivot] 大的，这又解释了前面算法的第二个步骤

A2 - 从右到左在 a[pivot + 1:] 里面找第一个值比 a[pivot] 大的索引（这个索引我们记作 r）

前面提到的算法还有最后两个步骤没有解释，这两个其实是互相关联的

Q3 - 为什么要交换 a[pivot] 和 a[r]，以及为什么随后要翻转 a[pivot + 1:]？

理论上来说，我们修改了 a[pivot] 的值之后，a[pivot + 1:] 这个部分也需要修改，那么问题是如何修改？从回溯的角度来看，a[pivot + 1:] 应该从最小字典序开始枚举，这意味着 a[pivot + 1:] 应该是非递减的。有趣的是，交换 a[pivot] 和 a[r] 之后，a[pivot + 1:] 这个后缀仍然是非递增的，那么我们要把它变成非递减的只需要翻转一下这个部分就行，这就解释了前面算法的第三步和第四步

A3 - 交换 a[pivot] 和 a[r] 之后 a[pivot + 1:] 仍然是非递增，翻转操作把这个后缀变成了非递减

代码

Leetcode 有一道题目可以练习，推荐先按照自己的理解动手实现下再参考下面的代码 :)

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        # Step 1. Find the rightmost i s.t. a[i] > a[i - 1]
        #         and set pivot to i - 1
        pivot = -1
        for i in reversed(range(len(nums))):
            if i - 1 >= 0 and nums[i] > nums[i - 1]:
                pivot = i - 1
                break
        if pivot == -1:
            nums.reverse() 
            return

        # Step 2. Find the rightmost value s.t. a[i] > a[pivot]
        for i in reversed(range(len(nums))):
            if nums[i] > nums[pivot]:
                nums[i], nums[pivot] = nums[pivot], nums[i]
                break

        # Step 3. Reverse the (pivot, len(nums)) part
        left, right = pivot + 1, len(nums) - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

        return None

总结

从回溯的角度来理解「下一个排列」问题的算法就很自然了（起码对我来说），希望你也能有所收获 :)

参考