洗牌算法详解

前言

前段时间在准备求职面试时，在一个销售公司的面试中，多次被问及如何实现一个洗牌算法。我对洗牌算法的了解仅限于在 Radash 函数库中见过相关函数，对此并不熟悉，于是后面就看了一下相关的代码实现，来学习一下。
洗牌算法的核心目标是将一个序列的元素顺序完全随机化，确保每种可能的排列出现的概率相等。本文将对几种经典的洗牌算法进行介绍。
Fisher-Yates

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

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

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

复制代码

正确性证明

考虑一个长度为 \(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\) 的数组：

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

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

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

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

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

复制代码

正确性证明

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)!\]
蓄水池抽样算法

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

[code]function reservoirSample(stream: Iterable, k: number): T[] {  const reservoir: T[] = []  let count = 0    for (const item of stream) {    count++;    if (count 1\) 的情况，证明思路类似。在处理第 \(i\) 个元素时（\(i > k\)），算法以 \(k/i\) 的概率决定是否将其纳入蓄水池，如果决定纳入，则再均匀随机地替换掉蓄水池中现有的一个元素。通过类似的概率链式乘法，可以证明每个元素最终出现在蓄水池中的概率均为 \(k/n\)。</p>对于第 \(m,m>k\) 个元素，最终被选中的概率等于它在第 \(m\) 步被选入蓄水池的概率，乘以在后续所有步骤中它没有被替换出去的概率。
在第 \(m\) 步，它被选入的概率是 \(k/m\)。
一旦被选入，它会在蓄水池中占据一个位置。后续每处理一个新元素（第 \(j,j>m\) 步），该新元素有 \(k/j\) 的概率被选入，并且如果被选入，它会以 \(1/k\) 的概率替换掉当前元素。因此，在第 \(j\) 步，当前元素被替换的概率为 \(\frac{k}j \times\frac{1}k=\frac{1}j\)。那么它存活（不被替换）的概率就是 \(\frac{j-1}j\)。
所以，从第 \(m+1\) 步到第 \(n\) 步，它都存活下来的概率为：

\[\frac{m}{m+1} \times \frac{m+1}{m+2} \times... \times\frac{n-1}n=\frac{m}n\]
因此，第 \(m\) 个元素最终被选中的概率为：\(\frac{m}n\times\frac{k}m=\frac{k}{n}\)。
对于前 \(k\) 个元素（即 \(m≤k\)），这些元素一开始就在蓄水池中，但后续可能被替换。它们最终被选中的概率等于它们在后续所有步骤中从未被替换的概率。
对于第 \(m,m≤k\) 个元素，它从第 \(k+1\) 步开始面临被替换的风险。同样，在第 \(j,j>k\) 步，它被替换的概率为 \(1/j\) ，存活概率为 \(\frac{j-1}j\)。
因此，从第 \(k+1\) 步到第 \(n\) 步，它一直存活下来的概率为：

\[\frac{k}{k+1}\times\frac{k+1}{k+2}\times...\times\frac{n-1}{n}=\frac{k}n\]
结语

洗牌算法虽然原理上并不复杂，但是它的设计极为巧妙。Fisher-Yates 算法提供了标准且高效的完全随机化方案，Sattolo 算法通过微小约束来满足完全错位的需求，而蓄水池抽样算法则可以突破数据必须全部在内存中的限制，优雅地处理流式数据。
大家的阅读是我发帖的动力，本文首发于我的博客：deer.shika-blog.xyz，欢迎大家来玩喵， 转载请注明出处。

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！