← 返回编程题库
coding-card-shuffle-bias-detection困难免费版5000ms未尝试

洗牌偏差检测:找出最被高估的排列

Card Shuffle Bias Detection

开始编码

蒙特卡洛模拟里有一类极其隐蔽的 bug:你以为自己在均匀洗牌,但你写的洗牌函数其实有偏。这种 bug 在交易策略回测、组合实验、A/B 测试随机分组等场景都出现过——某个本该等概率出现的事件被持续高估或低估,模拟结果和现实悄悄走偏,而你完全不知道。本题的目标是模拟一个标准的「偏差侦测」流程:给一个已知有偏的洗牌函数,跑大量样本,统计每个排列出现频次,找出最被高估的那一个。

stub.py 里给了一个故意写错的洗牌函数 biased_shuffle(deck, rng)

def biased_shuffle(deck, rng):
    n = len(deck)
    a = list(deck)
    for i in range(n):
        j = rng.randrange(n)        # bug: 应该是 rng.randrange(i, n)
        a[i], a[j] = a[j], a[i]
    return tuple(a)

这是经典的「naive shuffle」错误:对每个位置 i,j 是从 整个 [0, n) 里抽,而正确的 Fisher-Yates 应该从 [i, n) 里抽。直观地讲,这版洗牌总共有 nnn^n 条等概率执行路径,但只有 n!n! 个不同的排列结果,nnn^n 不能被 n!n! 整除(除了 n=1,2n=1, 2 这种边界情况),所以分配给各排列的路径数必然不均等。具体到 n=3n=3:27 条路径分配为 {4, 4, 4, 5, 5, 5}——三个排列每个占 5/27、另外三个每个占 4/27,前者的真实概率是 0.1852、后者只有 0.1481,相差近 25%。

请实现 solution(D, K, seed) -> list[int]:用一个 random.Random(seed) 跑 K 次 biased_shuffle((0, 1, ..., D-1), rng),统计每个排列出现的次数 c(p)c(p),对每个观察到的排列 pp 计算

excess(p)  =  c(p)KD! \mathrm{excess}(p) \;=\; c(p) - \frac{K}{D!}

返回 excess 最大的那个排列(不是绝对值最大——被低估的排列 excess 是负数,不参与)。如果多个排列 excess 并列最大,按字典序最小的那个返回。返回类型是 list[int](不是 tuple)。

例子:solution(3, 6000, 42) 应返回 [1, 0, 2]D=3D=3 时三个高频排列 (0,2,1)、(1,0,2)、(1,2,0) 的真实概率都是 5/27,而种子 42 下经过 6000 次模拟后 (1,0,2) 的样本计数恰好略高于另外两个。再看 solution(2, 1000, 5) 应返回 [0, 1]D=2D=2 是个有趣的小例外——朴素 shuffle 的 4 条等概率路径里恰好 2 条产生 (0,1)、2 条产生 (1,0),真实分布完全均匀;K=1000 次后两个排列计数差几个、但期望偏差是 0;按 tie-break 规则返回字典序更小的 [0, 1]。

实现陷阱有三:(1) 必须只创建一个 random.Random(seed) 并在所有 K 次循环之间共用——每次重新 seed 会让 K 次结果完全相同,统计意义全失。(2) 「最大 excess」是带符号的最大,不是 |excess| 最大;写 max(counts.values(), key=...) 时 key 必须是 c - K/D!,不能是 abs(c - K/D!)。(3) 不要枚举 D!D! 个排列再查表——未出现的排列 excess = K/D!-K/D! 已经是最差,最优排列必然在你 Counter 里观察到的那些当中;总复杂度 O(KD)O(K \cdot D) 即可。

约束条件

  • 1 ≤ D ≤ 5
  • 1 ≤ K ≤ 500000
  • seed 是非负整数
  • 返回 `list[int]`(注意是 Python list,不是 tuple;JSON 序列化才能严格相等)
  • 必须用 stub.py 提供的 `biased_shuffle(deck, rng)` 帮手;不能替换为 `random.shuffle` 或 numpy
  • 必须**仅**创建一个 `random.Random(seed)` 实例并在所有 K 次 shuffle 之间共用,否则结果不可重现
  • tie-break:多个排列偏差并列最大时返回字典序最小的那一个

样例

Case 1 · D=3, K=6000, seed=42 — naive 3-card shuffle, classic bias

输入: [3,6000,42]

期望: [1,0,2]

D=3 时一共 3!=6 个排列,朴素 shuffle 共有 3^3=27 条等概率执行路径,理论分布为:(0,1,2)、(2,0,1)、(2,1,0) 各占 4/27;(0,2,1)、(1,0,2)、(1,2,0) 各占 5/27。后三个排列的真实概率高于均匀分布 1/6,所以在 K=6000 次模拟下其中之一会成为「最被高估」的排列。具体哪一个取决于随机种子产生的有限样本扰动;seed=42 下结果是 (1,0,2)。注意答案返回 Python `list` 而不是 tuple。

Case 2 · D=4, K=24000, seed=7 — bias becomes visible at scale

输入: [4,24000,7]

期望: [1,0,3,2]

D=4 时 4!=24 个排列,K=24000 意味着均匀期望计数为 1000/排列,但朴素 shuffle 在 D≥3 时会让大约一半的排列被「高估」、另一半被「低估」。seed=7 下被最高估的是 (1,0,3,2)——一个把相邻两对都对换的排列。如果你的实现忘了使用题目给的 `biased_shuffle` 帮手、或调用方式不对(例如每次新建 RNG),结果会与期望不符。

最近提交

还没有提交记录。

编码区

实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。

加载编辑器...
计时0:00

默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。

Case 1 · D=3, K=6000, seed=42 — naive 3-card shuffle, classic bias

输入: [3,6000,42]

期望: [1,0,2]

D=3 时一共 3!=6 个排列,朴素 shuffle 共有 3^3=27 条等概率执行路径,理论分布为:(0,1,2)、(2,0,1)、(2,1,0) 各占 4/27;(0,2,1)、(1,0,2)、(1,2,0) 各占 5/27。后三个排列的真实概率高于均匀分布 1/6,所以在 K=6000 次模拟下其中之一会成为「最被高估」的排列。具体哪一个取决于随机种子产生的有限样本扰动;seed=42 下结果是 (1,0,2)。注意答案返回 Python `list` 而不是 tuple。

Case 2 · D=4, K=24000, seed=7 — bias becomes visible at scale

输入: [4,24000,7]

期望: [1,0,3,2]

D=4 时 4!=24 个排列,K=24000 意味着均匀期望计数为 1000/排列,但朴素 shuffle 在 D≥3 时会让大约一半的排列被「高估」、另一半被「低估」。seed=7 下被最高估的是 (1,0,3,2)——一个把相邻两对都对换的排列。如果你的实现忘了使用题目给的 `biased_shuffle` 帮手、或调用方式不对(例如每次新建 RNG),结果会与期望不符。