编程语言研究书库
JavaScript 数据结构与算法

第 8 章 洗牌与采样 — 随机性的纪律

第 8 章 洗牌与采样 — 随机性的纪律

这一章讲什么: 两个依赖随机数的问题——把数组打乱(洗牌,生成随机排列) 和从数组里随机抽一小把(采样,生成随机组合)。它在全书链条里的位置: 第 6、7 章的「确定性算法」第一次全面遇到随机性;本章立下的规矩 (均匀性要证、要测,错一点不会报错)在第 12 章(随机化 BST)、 第 15 章(概率性堆)还会再用。

1. 顶层全景

  基础:Math.random() 给出 [0,1) 均匀伪随机数
      │  randomInt(a,b) = a + floor((b-a)*random())  → [a,b) 整数
      │  (掷骰子要写 randomInt(1,7)——上开区间,差一位就是错)
      │
      ├─ 洗牌(生成均匀排列:n! 种结果等概率)
      │    随机键排序     O(n log n) 最短但非最优
      │    抛硬币分治     平均 O(n log n),最坏 O(n²)
      │    Floyd 随机插入 思路美,数组实现 O(n²)
      │    Robson 阶乘编码 O(n),但 n! 超 JS 精度(n≤18)
      │    Fisher-Yates  O(n) 正主:从尾往头,位置 i 与 [from,i] 随机位交换
      │
      └─ 采样(抽 k 个:有重复?要保序?数据全在内存?)
           有重复:        逐次 singlePick,O(k)
           无重复 离线:   Floyd 递推 / 抽签 lottery O(k) / Fisher-Yates 采前段 O(k)
           无重复 保序:   Knuth 概率流(选中率 k/(剩余数))
           无重复 在线:   蓄水池采样(第 i 个以 k/i 概率替换库中随机一格)

  图说:洗牌的答案是 Fisher-Yates;采样的答案取决于三个开关:重复?保序?在线?

2. 主线例子:四张牌的 Fisher-Yates 走查 + 两个「看起来对」的错版

正主走查。 数组 [A, B, C, D](from=0, to=3),从尾往头:

  i=4:  j = randomInt(0, 4)  → 假设 j=1,交换位置 3 与 1:[A, D, C, B]
  i=3:  j = randomInt(0, 3)  → 假设 j=0,交换位置 2 与 0:[C, D, A, B]
  i=2:  j = randomInt(0, 2)  → 假设 j=1,交换位置 1 与 1(自己):[C, D, A, B]
  结束。一次洗牌共 4×3×2 = 24 种等概率的随机选择序列 = 4! 种排列,一一对应。

为什么是均匀的关键:第 i 步时,位置 i−1 从「还没定死的 i 个位置」里等概率选 ——每个元素最终落在每个位置的概率都被迫相等1。

错版一(习题 8.3,随机比较器): 把冒泡排序的比较换成「随机位决定换不换」。 直觉上「随机地排」应该随机,实际大谬:初始值要挪到末尾,必须一路上每次随机位 都为真,概率指数级小——元素基本留在原地附近,末尾位置几乎永远是原来的大值2。

错版二(习题 8.4,全域随机交换): 每轮从 [0, n) 全域随机选 j 与 i 交换。 这次随机序列有 nⁿ 种,而排列只有 n! 种——nⁿ 不是 n! 的整数倍, 有些排列被更多随机序列产生,分布必然不均匀(3 元素时 27 条序列分 6 种排列, 验算可见偏向)3。

这两条合起来是本章的纪律:「随机算法错了不会报错,只会悄悄不均匀」; 均匀性要么证(计数论证),要么测(习题 8.1 的直方图测试,48,000 次跑 4! 种 排列看频次)4。

3. 核心原理

3.1 基础工具与第一个坑

Math.random() 返回 [0, 1) 的伪随机数——由算法生成、看着随机但不是真随机 (书里的 NOTE 说明:由程序生成的序列必然不真随机,本章当随机用)5。 randomInt(a, b) 取 [a, b) 区间整数,前闭后开——掷骰子要 randomInt(1, 7), 写 (1, 6) 的人排着队掉进这个坑6。

3.2 洗牌五算法:从「能用」到「正确且最优」

随机键排序三行:每个值配个随机键、按键排序、丢掉键——O(n log n), 最短实现,也是采样版(8.8)的基础7。

抛硬币分治是快排划分的随机版:抛硬币把元素分进两组,递归洗牌各组。 平均 O(n log n)、最坏 O(n²),没赢过排序8。

Floyd 随机插入:像理牌,新数字随机插进已生成的序列——splice 在数组上 O(n),整体 O(n²);Floyd 本人建议哈希表(期望 O(n))或平衡树(O(n log n)) 装这个序列,那是第 11/12 章的结构9。

Robson 阶乘编码:n 个元素有 n! 种排列,那就均匀取一个 [0, n!) 的随机数, 不断「除以 i 取余」把余数翻译成逐位选择(余数选第几个、商继续)——O(n) 且 数学上完美对应(Lehmer 码一族)10。但 n! 会爆 JS 精度:18! 是上限, 19! 就丢了(习题 8.5;用 BigInt 可以更大,但失去「普通数」的便利)11。

Fisher-Yates(也作 Knuth shuffle):Robson 的务实版——不需要先算 n!, 余数直接用 randomInt 现场生成:

const fisherYatesShuffle = (arr, from = 0, to = arr.length - 1) => {
  for (let i = to + 1; i > from + 1; i--) {
    const j = randomInt(from, i);
    [arr[i - 1], arr[j]] = [arr[j], arr[i - 1]];
  }
  return arr;
};

O(n)、原地、均匀——三样全占,日常唯一该用的洗牌1。

3.3 采样的三个判定问题

第一问:允许重复? 允许就逐个 randomInt 取,k 次独立——O(k),平凡12。

第二问:离线,要不要保序?

  • 不保序:Floyd 采样(递归:sample(k−1, n−1) 后,以 1/n 概率取新值 n−1、 撞车了就用 n−1 顶替随机格;可证每个值入选概率恰为 k/n)13; 或抽签式:每轮取前 n−i 中的随机一个,取走的与末尾交换——O(k) 最优, 因为输出本身就有 k 个元素14。
  • 要保序:Knuth 流式采样——第 i 个元素以「还需选 k′ / 还剩 n′」的概率入选; 数学上直接由条件概率定义证明正确,还天然单遍15。 习题 8.10 解释为何不需要越界检查:一旦 toSelect === toConsider, 概率变 1,剩下的全会选中16。

第三问:在线(数据流式到来、不知道总长)? 蓄水池采样(Alan Waterman):前 k 个先装满蓄水池;之后第 i 个元素以 k/i 的 概率踢掉池中随机一个。任意时刻停手,池子都是已见数据的均匀 k 样本—— 内存只要 O(k),大流场景的唯一正解17。

4. 作者的判断与证据

  • 「洗牌难验证」被明说为全章动机:排序能查「真有序」、选择能查「值正确」, 洗牌的均匀性「没法直接查」——所以给了证(计数)与测(直方图)两条路18。
  • Fisher-Yates 的正当性来自计数论证(n! 与随机序列一一对应), 两个错版的诊断也是计数论证(nⁿ ≠ n! 的倍数)——全章方法论统一3。
  • 性能结论的边界都给了:Floyd 洗牌「数组版 O(n²),本人建议哈希/树」; Robson「O(n) 但 n≤18」;抽签「O(k) 不可再优」。没有无条件的「最好」9。
  • 直方图测试的统计学谦虚:48,000 次看着均匀「在统计意义上并不构成证明, 要做 χ² 拟合优度检验」——作者明确划了自己演示的界限4。

判断(我们的,不是书里的): 本章最该带走的是那句没说出口的元规则: 「随机性的正确性是计数问题,不是感觉问题」——均匀性 = 随机源的等可能 序列与目标对象(排列/组合)之间的一一对应。两个错版习题之所以好, 正因为它们的 bug 不在代码而在计数结构(nⁿ 对 n!)。记住这个判据, 日后评审任何「随机化」代码都有了第一问:你的随机序列数能被结果数整除吗? 如果错,会错在: 一一对应是充分条件而非必要条件——存在均匀但不一一对应的 算法(某些拒绝采样);作为评审启发式它极好,作为数学判据它偏窄。

5. 边界与局限

  • 伪随机数的质量没讨论:Math.random() 的具体引擎、种子、密码学适用性 都不在范围——书开头就说「当随机用」5。
  • 随机源只假定为均匀:如何把有偏的随机源变成均匀(randomness extraction) 没讲;习题 8.2 的「用 randomBit 造骰子」是最小版本的练习19。
  • 蓄水池采样的加权变体、分布式版本没有——只有等权在线基础版。
  • χ² 检验只点名不教;统计学读者需要另备材料4。

6. 可带走的

  1. randomInt(a, b) 是前闭后开;掷骰子写 randomInt(1, 7)。
  2. 洗牌默认 Fisher-Yates:从尾往头,位置 i−1 与 [from, i] 随机位交换;O(n)、原地、均匀。
  3. 随机算法错不报错,只悄悄不均匀——均匀性靠计数论证或直方图实测。
  4. 两个经典错版认脸:随机比较器排序(元素黏在原地)、全域随机交换(nⁿ 不是 n! 倍数)。
  5. Robson 阶乘编码 O(n) 且优美,但 n! 爆精度,n ≤ 18。
  6. 采样三开关:重复?(逐个取)/ 保序?(Knuth 概率流)/ 在线?(蓄水池 k/i)。
  7. 抽签式采样 O(k) 是最优复杂度,输出有 k 个元素就至少要碰 k 次。
  8. 测随机性:固定输入跑几万次,数每种结果的频次画直方图;严格判据是 χ² 检验。

7. 原文地图

主题原书章原文位置
伪随机与 randomIntChoosing Numbers Randomlytext/24-fm-choosing-numbers-randomly.txt:26(搜「pseudorandom」) · text/24-fm-choosing-numbers-randomly.txt:47(搜「rolling a die」)
洗牌难验证Choosing Numbers Randomlytext/24-fm-choosing-numbers-randomly.txt:63(搜「equally likely」)
随机键排序Choosing Numbers Randomlytext/24-fm-choosing-numbers-randomly.txt:85(搜「sortingShuffle」)
抛硬币分治Choosing Numbers Randomlytext/24-fm-choosing-numbers-randomly.txt:120(搜「coinTossingShuffle」)
Floyd 洗牌Choosing Numbers Randomlytext/24-fm-choosing-numbers-randomly.txt:181(搜「floydShuffleN」) · text/24-fm-choosing-numbers-randomly.txt:212(搜「hash table」)
Robson 与 Lehmer 码Choosing Numbers Randomlytext/24-fm-choosing-numbers-randomly.txt:253(搜「robsonShuffle」) · text/24-fm-choosing-numbers-randomly.txt:230(搜「Lehmer」)
Fisher-YatesChoosing Numbers Randomlytext/24-fm-choosing-numbers-randomly.txt:282(搜「fisherYatesShuffle」)
有重复采样Choosing Numbers Randomlytext/24-fm-choosing-numbers-randomly.txt:360(搜「repeatedPick」)
Floyd 采样Choosing Numbers Randomlytext/24-fm-choosing-numbers-randomly.txt:435(搜「floydSampleKofN」) · text/24-fm-choosing-numbers-randomly.txt:451(搜「3/8」)
抽签与 FY 采样Choosing Numbers Randomlytext/24-fm-choosing-numbers-randomly.txt:492(搜「lotterySample」) · text/24-fm-choosing-numbers-randomly.txt:528(搜「fisherYatesSample」)
Knuth 保序采样Choosing Numbers Randomlytext/24-fm-choosing-numbers-randomly.txt:558(搜「orderedSample」)
蓄水池采样Choosing Numbers Randomlytext/24-fm-choosing-numbers-randomly.txt:644(搜「reservoirSample」)
答案(直方图/错版诊断/精度上限)Chapter 8text/71-ch08-chapter-8.txt:10(搜「logResults」) · text/71-ch08-chapter-8.txt:73(搜「far more likely」) · text/71-ch08-chapter-8.txt:79(搜「27 possible」) · text/71-ch08-chapter-8.txt:85(搜「largest factorial」)

Footnotes

  1. 出处:「Choosing Numbers Randomly」第 276–302 段(text/24-fm-choosing-numbers-randomly.txt:282,搜「fisherYatesShuffle」)。原文:从尾往头,j = randomInt(from, i),交换 i−1 与 j;「Robson 的关键是余数序列,余数可以现场用随机函数生成」;「很高效,常用——但很容易写错(见习题 8.4)」。 ↩ ↩2

  2. 出处:「Chapter 8」第 73 段(text/71-ch08-chapter-8.txt:73,搜「far more likely」)。答案原文:初始值要到末尾需全部 randomBit 为真,「初始值多半落在离起点不远的地方,很少出现在末位」。 ↩

  3. 出处:「Chapter 8」第 79 段(text/71-ch08-chapter-8.txt:79,搜「27 possible」)。答案原文:循环 n 次、每次 n 种选择,共 nⁿ 种运行;「排列生成算法应只有 n! 种运行」;3 元素时 27 条序列分 6 种排列,分布不匀。 ↩ ↩2

  4. 出处:「Choosing Numbers Randomly」第 66 段(text/24-fm-choosing-numbers-randomly.txt:66,搜「statistically」)与「Choosing Numbers Randomly」第 710 段(text/24-fm-choosing-numbers-randomly.txt:710,搜「goodness-of-fit」)。原文:实证建议跑多次做统计;48,000 次后 24 种排列都出现且频次相近,「但统计意义上不构成断言,需要 χ² 拟合优度检验」。 ↩ ↩2 ↩3

  5. 出处:「Choosing Numbers Randomly」第 34 段(text/24-fm-choosing-numbers-randomly.txt:34,搜「pseudorandom」)。原文注:随机数由算法产生,「属性近似真随机,但由程序生成意味着不真随机;为简单本章当作随机」。 ↩ ↩2

  6. 出处:「Choosing Numbers Randomly」第 47 段(text/24-fm-choosing-numbers-randomly.txt:47,搜「rolling a die」)。原文:模拟骰子写 randomInt(1,6) 不行,randomInt(1,7) 才行;与 array.slice(start,end) 同口径,取 start 不取 end。 ↩

  7. 出处:「Choosing Numbers Randomly」第 85–90 段(text/24-fm-choosing-numbers-randomly.txt:85,搜「sortingShuffle」)。原文:配随机键、排序、取回值;「可能是全书最短的算法」;O(n log n)。 ↩

  8. 出处:「Choosing Numbers Randomly」第 120–149 段(text/24-fm-choosing-numbers-randomly.txt:120,搜「coinTossingShuffle」)。原文:抛硬币把元素分两组、递归洗牌;「平均 O(n log n),最坏 O(n²)——与排序相比并无进步」。 ↩

  9. 出处:「Choosing Numbers Randomly」第 181–212 段(text/24-fm-choosing-numbers-randomly.txt:181,搜「floydShuffleN」)。原文:新数随机插入已洗序列;数组 + splice 是 O(n²);Floyd 建议 2n 大小的哈希表装链表(期望 O(n))或带链平衡树(O(n log n))。 ↩ ↩2

  10. 出处:「Choosing Numbers Randomly」第 253–263 段(text/24-fm-choosing-numbers-randomly.txt:253,搜「robsonShuffle」)。原文:随机取 [0, n!) 的 r,循环中 q = r % i 选位交换、r = floor(r/i);「显然 O(n)」;Lehmer 码见第 230 段注。 ↩

  11. 出处:「Chapter 8」第 85–102 段(text/71-ch08-chapter-8.txt:85,搜「largest factorial」)。答案原文:普通精度最大算到 18!,19! 超界;判法是 fact < fact + 1 不再成立;BigInt 可更大直到内存耗尽。 ↩

  12. 出处:「Choosing Numbers Randomly」第 360–377 段(text/24-fm-choosing-numbers-randomly.txt:360,搜「repeatedPick」)。原文:循环 k 次独立 singlePick;应用:轮盘模拟、石头剪刀布策略、第 7 章 lazy select。 ↩

  13. 出处:「Choosing Numbers Randomly」第 435–465 段(text/24-fm-choosing-numbers-randomly.txt:435,搜「floydSampleKofN」)。原文:递归版先取 (k−1, n−1) 再决定加 j 还是 n−1;「7 入样的概率 = 1/8 + 2/8 = 3/8,正是所需」;迭代版循环 n−k 到 n−1。性能关键在集合的 includes 检查(第 468 段)。 ↩

  14. 出处:「Choosing Numbers Randomly」第 492–507 段(text/24-fm-choosing-numbers-randomly.txt:492,搜「lotterySample」)。原文:取走的与末尾交换避免搬移;「O(k) 不可再优——你总归要产出 k 个元素」。 ↩

  15. 出处:「Choosing Numbers Randomly」第 552–586 段(text/24-fm-choosing-numbers-randomly.txt:552,搜「3/8」)。原文:3/8 出 8 的第一个元素入选;入选后剩 2/7、未选则 3/7;实现用 toSelect/toConsider 计数。 ↩

  16. 出处:「Chapter 8」第 202 段(text/71-ch08-chapter-8.txt:202,搜「toSelect is not greater」)。答案原文:一旦 toSelect === toConsider,概率为 1、必全选,故 i 不会越界。 ↩

  17. 出处:「Choosing Numbers Randomly」第 613–656 段(text/24-fm-choosing-numbers-randomly.txt:613,搜「Waterman」)。原文:「可以在线工作,不必事先有整个数组;随时停手都是已见数据的合理随机样本」;前 k 个装满,第 i 个以 k/i 概率替换池中随机位。单元素版概率 1/i 的推导见第 627 段。 ↩

  18. 出处:「Choosing Numbers Randomly」第 63 段(text/24-fm-choosing-numbers-randomly.txt:63,搜「harder to check」)。原文:排序可验序、选择可验值,「洗牌更难检查」。 ↩

  19. 出处:「Chapter 8」第 41–67 段(text/71-ch08-chapter-8.txt:41,搜「four combinations」)。答案原文:两币造三选一(丢弃第 4 种重试);三币造骰子;D20 用 6 币取 0–59 除 3,丢弃率 4/64 更优。 ↩

第 7 章 选择 — 只找第 k 小,不必全排序

Previous Page

第 9 章 搜索 — 无序靠线性,有序靠折半

Next Page

On this page

第 8 章 洗牌与采样 — 随机性的纪律1. 顶层全景2. 主线例子:四张牌的 Fisher-Yates 走查 + 两个「看起来对」的错版3. 核心原理3.1 基础工具与第一个坑3.2 洗牌五算法:从「能用」到「正确且最优」3.3 采样的三个判定问题4. 作者的判断与证据5. 边界与局限6. 可带走的7. 原文地图Footnotes