函数式 Leetcode 百题 – 排列

§前言

算法题，是很多程序员的梦魇之一。算法本身当然是有趣的，但不会做题的抓狂、面试回答不出问题的窘迫，没有人会喜欢。

应对算法题挑战的传统方式是 刷题 。 刷题，也就是做大量的题目来学习算法。很多人笃信一种理论，无论是数学学习还是算法学习，都必须进行大量的练习。

我也认同这种理论。冯诺依曼的箴言还挂在本博客的首页上：

Young man, in mathematics you don’t understand things. You just get used to them.

直觉的认识，直觉的经验，是无比宝贵的财富。练习是获取这种宝贵财富最可靠的手段。简而言之，想要学习算法，你必须刷题，必须练习。

然而，我确实极度厌烦一种算法学习的常规路径。那就是看到某道题不会做，思考了 10 分钟还是不知道从何入手，那么就去寻找答案。也许你 理解 了答案或者记住了答案，下次看到相同的题目的时候就套进去。只要你见过的答案够多，那么你能 套 的题目也够多。

为什么我不喜欢这种学习方法呢？也许是我不够聪明吧，我很难 理解 别人给的答案。太多的人只是把最后的高效算法告诉你，而忽略了直觉建立的过程，更别提算法的证明了。从这些人的答案里，我既没有感受到他们对于问题的深刻理解，又没有感受到算法本身的美感。

难道我们只能通过给 天才 设计的教育来学习算法吗？

不。世界上还有一群人，在尝试着用纯函数式的语言，用等式推导的方法来设计程序。这些人同样也珍视直觉的价值。他们会从一个清晰而不高效的程序出发，一步步地给出最终的高效算法。在这个过程中，算法的美、算法的 insight 纤毫毕现。已故的 Richard Bird，台湾的穆信成老师都是这种方式的先驱。在他们的论文和书籍中，我感受到了一种真正的温柔。

我想，虽然等式推导很多时候非常困难，但是把算法的 non-trivial 之处是什么、算法的直觉是什么讲清楚，也许没有那么困难。

本系列文章就是我的尝试。我将在这些文章中，讲解我是怎么用纯函数式编程解决 Leetcode 的。至于为什么选择 Leetcode 而不是难度更高的 Codeforces，我认为难度太高，也许不是好事。高难度的问题很可能需要多个算法共同来处理，而我们更想在每篇文章中关注某类具体的算法。（另一个原因是，我本人对于算法仍然是某种意义的 初学者，难度太高我也处理不来）

选择 Leetcode 的一个后果是，我们必须用 Racket 或者 Scala 而非 Haskell 来提交代码。这有时候会造成一些困扰，不过我的经验是，大部分我给出的 Haskell 代码可以直接翻译到 Scala 上。每道题目我也会给出对应的 Scala 解。如果确实有问题，比如 Scala 没有 Data.Graph 这种不可变数据结构库，那么我们会视情况退回到非纯函数式编程。不过，这种情况总体应该是较少的。在每道题目的最后，我可能也会把对应的命令式版本给出，也许我们还会探讨一下函数式版本和命令式版本的区别。

这些文章不是 函数式编程入门。虽然我也许会提示某个库函数的用法，但是总体来说，这些文章假设你已经有了纯函数式编程的基本知识 – 递归，列表，fold，map 等等。如果你对函数式编程和 Haskell 语言一无所知，那么在阅读这些文章之前最好简单学习一些 Haskell 知识。以下是我比较推荐的学习资源：

路漫漫其修远兮，吾将上下而求索

§31. 下一个排列

§题目描述

以下是 Leetcode 的原始描述：

整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。

例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、`[3,1,2]、[2,3,1] 。 整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。 类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。 而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。 给你一个整数数组 nums ，找出 nums 的下一个排列。

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

我们是在纯函数式编程。纯函数式编程没有所谓的 修改，所以最后一句话我们无视即可。

§第一想法

一般来说，很多算法问题能够给一个极为简洁（但低效）的纯函数式解。我们把这个解称之为程序的标准参照（Spec），我们的思考也从这里出发。然而，这个问题却似乎不是这种情况。考虑这个问题的数学表达：

next(a)={min⁡(P)a=max⁡(P)min⁡({m∣m∈P,m>a})otherwise \text{next}(a) = \begin{cases} \min(\mathbb{P}) & a = \max(\mathbb{P}) \\ \min(\{ m | m \in \mathbb{P}, m > a \}) & \text{otherwise} \end{cases}

这没有给我们多少灵感。事实上，在很多编程语言里，把 P\mathbb{P}，也就是某个列表的所有排列求出来，比这个问题还要麻烦。1

这种情况下，一个直觉的尝试是，简单的递归 能不能解决问题呢？

§递归

下一个排列函数（记为 next）虽然定义在排列和字典序上，但却显然可以被推广到更泛化的结构上。

我们首先考查十进制整数的情况。显然地，十进制整数也可以定义 next 函数。这就是大名鼎鼎的 后继 函数，即 f(x)=x+1f(x) = x + 1 .

十进制整数可以被表示为一个列表（或者，命令式语言里的数组），列表中的每个元素表示数字的每一位。例如，100100 被表示为 [1, 0, 0] .

我们特别关心列表表示下的后继函数，因为在这种表示下，>= 恰恰就是字典序比较。我们把列表表示下，十进制整数的后继函数记作 next10.

1-- next10 [1, 1, 0] = [1, 1, 1]
2next10 ...

例如，next10 [1, 1, 0] = [1, 1, 1]。

这个例子给了我们非常强的直觉。那就是 next10 [1, 0] = [1, 1]，此时 next10 [1, 1, 0] = 1 : next10 [1, 0]. 把这种关系一般化，我们得到对于 x:xs 表示的整数，

1next10 (x:xs) = x:(next10 xs)

上式在大部分时候都成立。除非，next10 xs 已经 求不出来了，比如 [1, 9, 9] 的下一个数字（后继）是 [2, 0, 0]，这时就必须要 进位。更严格地说，99 是 最大 的两位十进制整数，所以上式不成立。可以证明，只要 xs 还不是最大值，那么上面的等式就成立。

类似地，同样可以证明题目要求的 next 函数具有同样的性质：当 xs 不是长度为 length xs 的排列的最大值时，

1next (x:xs) = x:next xs

这个性质实在太过重要，因为我们可以直接构造递归函数：

1next (x:xs)
2    | isMax xs  = tick x xs
3    | otherwise = x:next xs

那么，问题就变成了

  1. 如何定义 isMax
  2. 如果 xs 已经是最大值了，那么 tick 函数该怎么定义呢？

§isMax 的定义

对于一个排列 xs 来说，最大 就是说，无论怎么重新排列，新的 xs' 一定有 xs >= xs'.

什么样的排列具有这种性质呢？一个很自然的想法是，因为这是字典序，所以如果想要排列尽可能大，那就一定要把大的数放在前面。换句话说，降序 的排列一定是最大的。

1isMax :: Ord a => [a] -> Bool
2isMax = down

在 Haskell 里，判断一个列表的升降，我们可以使用 zip with tail 的方法。具体来说，就是首先把列表和它的 tail 进行 zip，然后再使用 map, all 之类的函数来判断。

1dup :: [a] -> [(a, a)]
2dup xs = zip xs (tail xs)
3
4down :: Ord a => [a] -> Bool
5down = all (uncurry (>=)) . dup

§tick 的定义

如果 xs 已经满足了 down，换言之，它已经是最大的了，那么 x:xs 必须要进行比较复杂的操作才能得到下一个枚举。这个复杂的操作，被我称为 tick.

例如，[2, 4, 3, 1] 的下一个枚举是 [3, 1, 2, 4]. 这时 x 是 2, xs 是 [4, 3, 1]，xs 满足 down，所以，这时不能再进行简单的递归，而要用 tick 进行计算。

继续以 [2, 4, 3, 1] 为例。直觉上来讲，要求 [2, 4, 3, 1] 的下一个枚举 ys@(y:ys'), 可以分为两步：

  • 确定 y 是什么
  • 确定 ys' 是什么

首先，y 要严格大于 x. 因为我们已经表明，所有以 x 开头的枚举都要比 x:xs 小。其次，y 要尽可能小，不然会有更小的枚举 p 满足 p > x:xs.

上例中 y 是 3. 很容易想到，3 是 xs = [4, 3, 1] 中，最小的 大于 x = 2 的数。我们把这种数叫做 pivot. 可以写出定义代码：

1pivot x xs = minumum [ x' | x' <- xs, x' > x  ]

注意到 xs 是有序的，以上代码可以改写为

1pivot x = last . takeWhile (> x)

需要指出的是，pivot 函数是一个偏函数，我们用了不安全的 last 和 minimum 操作，这意味着在调用时，必须保证至少存在一个 x' > x.

如果能够找到这样的 y > x，那么我们就可以保证，y:ys' 绝对比 x:xs 大。所以，ys' 的构造要使得 y:ys' 尽可能小。也就是说，ys' 应该是最小的一个排列。和我们上面对于最大值的讨论一样，最小的排列就是单调递增的排列。这只需要排序即可。

ys' 中的元素自然是 xs 除掉 y 之后，再加上 x. 例如，上面的例子 [2, 4, 3, 1]，可以给出

1x:xs = [2, 4, 3, 1]
2
3y = last . takeWhile (> x) $ xs
4  = last [4, 3]
5  = 3
6
7ys'' = delete 3 xs
8     = [4, 1]
9
10ys' = sort (x:ys'')
11    = sort [2, 4, 1]
12    = [1, 2, 4]
13
14ys = y:ys'
15   = [3, 1, 2, 4]

最后，还需要讨论一种情况，那就是 pivot x xs = ⊥. 这种情况必须先行判断，以免出现错误。什么时候 pivot 不存在呢？那就是 x:xs 已经满足 down 的时候，例如 [4, 3, 2, 1]，这种时候，只需要把输入反转即可。

根据以上讨论，我们给出 tick 函数的定义：

1import Data.List (delete)
2
3tick :: Ord a -> a -> [a] -> [a]
4tick x xs
5    | null l    = reverse (x:xs)
6    | otherwise = y:(sort (x:ys'))
7    where l = takeWhile (> x) xs
8          y = last l
9          ys' = delete y xs
1> tick 4 [3, 2, 1]
2[1, 2, 3, 4]
3
4> tick 2 [4, 3, 1]
5[3, 1, 2, 4]

毫无疑问，目前的 next 函数已经能够正确地解决这个问题了。读者不妨把以上的 Haskell 代码翻译为 Scala，在 Leetcode 里试一试。从递归出发，我们发现这个问题的解非常直觉，可以简单而轻松地给出。

§更高效的代码

上面定义的 next 函数虽然优雅直观，但是不够高效。主要的问题在于，

  1. tick 中，不需要用到 sort. xs 是有序的，可以利用这点在 O(n)O(n) 内把新的有序序列组合起来
  2. down 被 next 调用了好多次，每次调用都是 O(n)O(n) 的，导致总体复杂度出现了 O(n2)O(n^2).

问题 1. 很简单，只需要重新写一下 tick 即可。

问题 2. 比较麻烦。我们需要仔细观查一下计算的过程，例如 next [3, 5, 1, 4, 2]：

1next [3, 5, 1, 4, 2]
2= 3:(next [5, 1, 4, 2])
3= 3:(5:(next [1, 4, 2]))
4= 3:(5:(tick 1 [4, 2]))

可以看到，这个计算总是会具有一种 形状，那就是输入的前一部分保持不变，后一部分被 tick.

1[3, 5,           1, 4, 2]
2^^^^^^           #######
3保持不变的部分     tick 的部分

而它们的分界线，直觉上来讲，就是 down 由 False 变为 True 的时刻。我们再回到 next 函数：

1next (x:xs)
2    | down xs  = tick x xs
3    | otherwise = x:next xs

在每次递归的时候，next (x:xs) 都会计算 down xs，再用刚才的例子，

1-- 第一次递归
2down [5, 1, 4, 2] = False
3-- 第二次递归
4down [1, 4, 2]    = False
5-- 第三次递归
6down [4, 2]       = True

事实上，down 每次都顺序地计算 tails 里的下一个元素：

1> tails [3, 5, 1, 4, 2]
2[[3,5,1,4,2],[5,1,4,2],[1,4,2],[4,2],[2],[]]

不妨把 next 每次用到的 down xs 提前2算出来，并放到一个列表里

1import Data.List (tails)
2
3nextDown (x:xs) (d:ds)
4    | d = tick x xs
5    | otherwise = x:nextDown xs ds
6
7next xs = nextDown xs (downs xs)
8downs = drop 1 . map down . tails

如果我们可以在 O(n)O(n) 时间内算出 downs，问题 2. 就迎刃而解了。直觉上来说，这是很容易的，因为 down [4, 3, 2, 1] 本来就是要保证：

  • 4 >= 3
  • down [3, 2, 1]

换句话说，当我们要算 down [4, 3, 2, 1] 的时候，down [3, 2, 1] 已经被计算过了，只是需要一种方式把这种 上一次的计算 存起来以便后续使用。

函数式编程社区早就有了对于这种问题的解决方法： scan theorem.

Scan theorem 指的是

1map (foldl op a) . inits = scanl op a

类似地

1map (foldr op a) . tails = scanr op a

利用这个定理，我们给出以下程序计算过程. 注意，为了避免问题，我们定义了

1tails' = filter (not . null) . tails
1downs = { definition }
2        drop 1 . map down . tails'
3      = { definition }
4        drop 1 . map (all (uncurry (>=)) . dup) . tails'
5      = { map distributivity }
6        drop 1 . map (all (uncurry (>=))) . map dup . tails'
7      = { need another proof (1) }
8        drop 1 . map (all (uncurry (>=))) . tails . dup
9      = { definition }
10        drop 1 . map (foldr (&&) True . map (uncurry (>=))) . tails . dup
11      = { fold-map fusion }
12        drop 1 . map (foldr join True) . tails . dup
13      = { scan theorem }
14        drop 1 . scanr join True . dup
15          where join (x, x1) r = x >= x1 && r
  1. 需要一个新的证明，它指的是下面的代码是等价的：
1> map dup $ tails' [4, 2, 3, 1]
2[[(4,2),(2,3),(3,1)],[(2,3),(3,1)],[(3,1)],[]]
3
4> tails $ dup [4, 2, 3, 1]
5[[(4,2),(2,3),(3,1)],[(2,3),(3,1)],[(3,1)],[]]

证明略去。

§总结

结合上面的讨论，我们可以给出高效的函数式实现：

1tick x xs = build l r x
2    where (l, r) = span (> x) xs
3          build [] r x = reverse (x:r)
4          build l  r x = last l : reverse (init l ++ [x] ++ r)
5
6dup xs = zip xs (tail xs)
7downs = scanr (\(x, x1) r -> (x >= x1) && r) True . dup
8
9next xs = l ++ tick (head r) (tail r)
10    where (l, r) = splitAt (n - 1) xs
11          n = length $ takeWhile not $ downs xs

这是 O(n)O(n) 时间复杂度的。不过，我们的常数确实会比命令式程序大些。理论上来说，上一节定义的 nextDown 函数的实现要更高效一些（避免了 length 和 splitAt），但是我仍然觉得本节给出的实现更清楚。

我把等价的 Scala 代码提交到了 leetcode:

1object Solution {
2    def nextPermutation(nums: Array[Int]): Unit = {
3        val nextNums = next(nums.toList).toArray
4        for (i <- nums.indices) {
5            nums(i) = nextNums(i)
6        }
7    }
8
9    def dup(xs: List[Int]): List[(Int, Int)] = xs zip xs.drop(1)
10
11    def tick(x: Int, xs: List[Int]): List[Int] = {
12        val (l, r) = xs.span(_ > x)
13        if (l.isEmpty) r.reverse ++ List(x)
14        else l.last :: (l.init ++ List(x) ++ r).reverse
15    }
16
17    def tailsDown(xs: List[(Int, Int)]): List[Boolean] = 
18        xs.scanRight(true) { case ((x, x1), r) => (x >= x1) && r }
19
20    def next(xs: List[Int]): List[Int] = {
21        val n = tailsDown(dup(xs)).takeWhile(!_).length
22        val (l, r) = xs.splitAt(n - 1)
23        l ++ tick(r.head, r.tail)
24    }
25}

下一个排列 问题是少有的命令式程序可以比函数式程序简洁的问题。甚至，Haskell 的 Data.Permute 库，也用了命令式的方法。

在命令式程序中，上面的算法可以被描述为两个过程：

  1. 从右向左遍历，找到最长的下降序列 a[i…(len - 1)]a[i \dots (\text{len - 1})]
  2. 进行计算，

    • 如果 i=0i = 0，那么反转数组

    • 其他情况，找到 j∈[i,(len - 1)]j \in [i, \text{(len - 1)}]，使得

      • a[j]>a[i−1]a[j] > a[i - 1]
      • ∀k≥i,a[k]>a[i−1]→a[k]≥a[j]\forall k \ge i, a[k] > a[i - 1] \to a[k] \ge a[j]

      交换 i−1,ji - 1, j，反转 a[i…(len - 1)]a[i \dots (\text{len - 1})]

如果读者完全理解了上面的函数式算法，这个命令式算法想必是非常直白的。但如果把这个算法直接端到你的面前喂给你，你真的能明白它为什么是正确的吗？

让我们用一个 Python 程序结束今天的故事吧！

1def swap(a, i, j):
2    tmp = a[i]
3    a[i] = a[j]
4    a[j] = tmp
5
6def rev(a, start, end):
7    l = end - start
8    for i in range(start, start + l // 2):
9        swap(a, i, end - (i - start) - 1)
10
11def solve(a):
12    for i in range(len(a) - 1, -1, -1):
13        if i >= 1 and a[i - 1] < a[i]:
14            break
15    if i == 0:
16        rev(a, 0, len(a))
17    else:
18        j = len(a) - 1
19        while j >= i and a[j] <= a[i - 1]:
20            j -= 1
21        swap(a, i - 1, j)
22        rev(a, i, len(a))