前言

前段时间在准备求职面试时，在一个销售公司的面试中，多次被问及如何实现一个洗牌算法。我对洗牌算法的了解仅限于在 Radash 函数库中见过相关函数，对此并不熟悉，于是后面就看了一下相关的代码实现，来学习一下。

洗牌算法的核心目标是将一个序列的元素顺序完全随机化，确保每种可能的排列出现的概率相等。本文将对几种经典的洗牌算法进行介绍。

Fisher-Yates

Fisher-Yates 洗牌算法由 Ronald Fisher 和 Frank Yates 于1938年提出，是一种时间复杂度为 $O(n)$ 的洗牌算法。其基本思想是从序列的最后一个元素开始，随机选择一个从第一个元素到当前位置之间的元素进行交换，然后逐步向前移动，直到整个序列被遍历一次。

正确性的证明

考虑一个长度为 $n$ 的序列。算法的核心是从后向前处理每个位置：对于位置 $i$（从 $n-1$ 开始递减到 1），我们从 0 到 $i$ 之间随机选择一个位置 $j$，然后交换位置 $i$ 和位置 $j$ 的元素。

现在，我们关注任意一个特定元素最终出现在任意特定位置的概率。以元素 $x$ 最终出现在位置 $k$ 为例，看看这个概率是多少。

算法执行过程中，元素 $x$ 最终被放置到位置 $k$，需要满足两个条件：

• 在处理的每一步（从位置 $n-1$ 到位置 $k+1$），元素 $x$ 都没有被选中与当前处理的 $i$ 位置交换；
• 在轮到处理位置 $k$ 时，元素 $x$ 被选中与位置 $k$ 交换。

让我们计算这两个条件同时满足的概率：

当处理最后一个位置 $n-1$ 时，算法从所有 $n$ 个元素中随机选择一个放到这个位置。元素 $x$ 不被选中的概率是 $(n-1)/n$。

接着处理位置 $n-2$，此时剩余 $n-1$ 个元素（因为位置 $n-1$ 已确定），算法从这 $n-1$ 个元素中随机选择一个放到位置 $n-2$。元素 $x$ 不被选中的概率是 $(n-2)/(n-1)$。

依此类推，当处理到位置 $k+1$ 时，剩余 $k+2$ 个元素，元素 $x$ 不被选中的概率是 $(k+1)/(k+2)$。

最后，当处理到位置 $k$时，剩余 $k+1$ 个元素，算法从这 $k+1$ 个元素中随机选择一个放到位置 $k$。这时元素 $x$ 被选中的概率是 $1/(k+1)$。

将所有概率相乘：

$$(n-1)/n \times (n-2)/(n-1) \times ... \times (k+1)/(k+2) \times 1/(k+1) = 1/n$$

这意味着，任意一个元素最终出现在任意特定位置的概率都是 $1/n$。

此外，可以证明对于任意 $n,n \geq 1$，Fisher-Yates shuffle 生成任意特定排列 $\pi$ 的概率为 $1/n!$。

$n=1$，自然成立。假设对于 $n-1$ 长度的数组，算法生成某个任意的排列的概率为 $1/(n−1)!$。

考虑长度为 $n$ 的数组：

1. $i=n-1$，随机选择 $j \in [0,n-1]$，交换下标 $j$ 和 $n-1$，这意味着位置 $n-1$ 上的元素是从所有 $n$ 个元素中随即均匀选择的。对于任意特定元素，$x$ 选到 $n-1$ 上的概率是 $1/n$。
2. $i$ 继续向前移动，接下来的步骤是对 $[0,n-2]$ 上的元素继续使用 Fisher-Yates shuffle。根据归纳假设，这 $n-1$ 个元素生成特定排列的概率为 $1/(n−1)!$。

上述过程不依赖特定的 $x$ 和 $\pi$，因此，Fisher-Yates shuffle 生成任意特定排列 $π$ 的概率为 $1/n!$。

代码实现

它也有前向和原地交换的版本，原理上都一样的。

typescript
function fisherYatesShuffle<T>(array: T[]): T[] {
  const shuffled = [...array]
  for (let i = shuffled.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1))
    [shuffled[i], shuffled[j]] = [shuffled[j], shuffled[i]]
  }
  return shuffled
}

Sattolo 算法

Sattolo 算法是 Fisher-Yates 算法的一个变种，由 Sandra Sattolo 于1986年提出。它与 Fisher-Yates 算法的唯一区别在于：在每一步中，随机选择的索引 $j$ 的范围是 $[0, i-1]$，而不是 $[0, i]$。这个细微的修改导致算法产生的排列是一个随机的循环排列，即每个元素都不停留在其原始位置上。

正确性证明

Sattolo 算法生成的是一个长度为 $n$ 的随机循环排列。所谓循环排列，是指排列可以被表示为若干个不相交的循环，且整个排列本身构成一个单一的循环（即从任一元素开始，通过重复应用排列映射，可以遍历所有元素后回到起点）。

类似地，我们可以知道，对于每一个下标 $i$ 的元素，放在某个下标 $k, k \not= i$ 中的概率是

$$(n-2)/(n-1) \times (n-3)/(n-2) \times ... \times k/(k+1) \times 1/k = 1/(n-1),k>0\\ (n-2)/(n-1) \times (n-3)/(n-2) \times ... \times 2/3 \times 1/2 = 1/(n-1),k=0$$

在算法的每一步中，由于下标 $j$ 的取值范围排除了 $i$ 本身，这确保了下标 $i$ 元素不会与自身交换，从而不会被放回原位。更重要的是，这种选择方式强制在排列图中形成一条边从 $i$ 指向 $j$，最终这些边必然构成一个单一的循环。

可以证明，Sattolo 算法均匀地生成所有可能的 $(n-1)!$ 个循环排列。直观理解是，在第一步（处理索引 $n-1$），我们有 $n-1$ 种选择来建立一条边；在后续的每一步，可用的选择数递减，但整体上每个循环排列的生成路径都是唯一且等概率的，概率为

$$1/(n-1) \times 1/(n-2) \times ... \times 1/1 = 1/(n-1)!$$

代码实现

一样的，也有前向和原地修改的版本。

typescript
function sattoloShuffle<T>(array: T[]): T[] {
  const shuffled = [...array]
  for (let i = shuffled.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * i)
    [shuffled[i], shuffled[j]] = [shuffled[j], shuffled[i]]
  }
  return shuffled
}

蓄水池抽样算法

蓄水池抽样算法用于解决这样一个问题：当数据的总量 n 非常大或者未知时，如何从中等概率地随机抽取 $k$ 个样本。该算法只需对数据进行一次遍历，且仅需 $O(k)$ 的额外内存空间。当 $k=1$ 时，可以看作是对整个“数据流”进行一种特殊的“洗牌”，最终随机获得一个元素；当 $k>1$ 时，它可以看作是从流动的数据中动态维护一个随机样本集。

正确性证明

我们首先证明 $k=1$ 的情况的正确性。算法维护一个变量 $reservoir$ 作为当前的候选样本。当处理第 $i$ 个元素（$i$ 从 1 开始计数）时，算法以 $1/i$ 的概率选择用新元素替换 $reservoir$ 中的当前值。

对于任意一个索引为 $m$ 的元素，它最终被选为样本的概率，等于它在第 $m$ 步被选入蓄水池的概率，乘以在后续所有步骤中都没有被替换出去的概率。具体计算为：

$$1/m \times m/(m+1) \times (m+1)/(m+2) \times ... \times (n-1)/n = 1/n$$

因此，每个元素被选中的概率都是相等的 $1/n$。

对于一般的 $k>1$ 的情况，证明思路类似。在处理第 $i$ 个元素时（$i > k$），算法以 $k/i$ 的概率决定是否将其纳入蓄水池，如果决定纳入，则再均匀随机地替换掉蓄水池中现有的一个元素。通过类似的概率链式乘法，可以证明每个元素最终出现在蓄水池中的概率均为 $k/n$。

代码实现

typescript
function reservoirSample<T>(stream: Iterable<T>, k: number): T[] {
  const reservoir: T[] = []
  let count = 0
  
  for (const item of stream) {
    count++;
    if (count <= k) {
      reservoir.push(item);
    } else {
      const replaceIndex = Math.floor(Math.random() * count)
      if (replaceIndex < k) {
        reservoir[replaceIndex] = item
      }
    }
  }
  return reservoir
}

结语

洗牌算法虽然原理上并不复杂，但是它的设计极为巧妙。Fisher-Yates 算法提供了标准且高效的完全随机化方案，Sattolo 算法则展示了如何通过微小约束来满足“完全错位”的特定需求，而蓄水池抽样算法则突破了数据必须全部在内存中的限制，优雅地处理了流式数据。