洗牌偏差检测:找出最被高估的排列
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) 里抽。直观地讲,这版洗牌总共有 条等概率执行路径,但只有 个不同的排列结果, 不能被 整除(除了 这种边界情况),所以分配给各排列的路径数必然不均等。具体到 :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),统计每个排列出现的次数 ,对每个观察到的排列 计算
返回 excess 最大的那个排列(不是绝对值最大——被低估的排列 excess 是负数,不参与)。如果多个排列 excess 并列最大,按字典序最小的那个返回。返回类型是 list[int](不是 tuple)。
例子:solution(3, 6000, 42) 应返回 [1, 0, 2]。 时三个高频排列 (0,2,1)、(1,0,2)、(1,2,0) 的真实概率都是 5/27,而种子 42 下经过 6000 次模拟后 (1,0,2) 的样本计数恰好略高于另外两个。再看 solution(2, 1000, 5) 应返回 [0, 1]: 是个有趣的小例外——朴素 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) 不要枚举 个排列再查表——未出现的排列 excess = 已经是最差,最优排列必然在你 Counter 里观察到的那些当中;总复杂度 即可。
约束条件
- 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 可见样例;服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。
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),结果会与期望不符。