用rand7实现rand10：拒绝采样原理、优化与常见误区

刷题刷到随机数这块LeetCode 470 基本是绕不开的一道题。题目很短一句话给你一个能等概率生成 1 到 7 的 rand7()要求只基于它实现 rand10()让输出 1 到 10 也等概率。很多人第一眼觉得应该很简单写出来的代码却经不起推敲。我最早刷这道题的时候也想当然地写过(rand7() rand7()) % 10 1这种写法被测试数据教育了之后才老老实实去查为什么。后来在面试里也遇到过几次这道题的变体比如用 rand5() 生成 rand7()本质上都和拒绝采样有关。所以这篇文章我把自己从错误到正确、从基础到优化的完整思路写出来顺便把常见误区和证明方法也整理清楚希望能帮你一次吃透这道经典概率题。1. 题目到底在考什么为什么不能简单硬凑1.1 单次调用的信息量不够先从最底层想这个问题。rand7()的输出只有 7 种可能而目标rand10()需要 10 种可能。一次rand7()无论如何也没法直接变出 10 种等概率结果因为 7 不是 10 的倍数。这句话看着像废话但很多人写错代码就是因为忽略了这一点。有人会想那我把rand7()的结果乘一个系数不就行了比如rand7() * 10 // 7。问题是乘法缩放只能放大数值区间不能改变每个值出现的概率更没法凭空多出几种等概率的结果来。rand7()的结果 1 到 7 本来就是等概率的经过线性变换后还是 7 个等概率的值不可能均匀覆盖 1 到 10 这 10 个整数。所以核心思路只能是多次调用rand7()用它们的组合结果来构造一个更大的、仍然是等概率的样本空间然后从这个大空间里提取目标结果。这里的组合方式必须保证每个组合出现的概率完全相等否则后面全是白搭。1.2 组合二维坐标把 1 到 49 当成一副等概率卡牌常见的组合方式是调用两次rand7()。假设第一次叫a第二次叫b那么(a, b)一共有 7×749 种组合而且每种组合出现的概率都是 1/49。看起来很简单但怎么把 49 种等概率组合映射成 10 种等概率结果一个很自然的做法是构造一个公式num (a - 1) * 7 b这个num的取值范围是 1 到 49。你可以把它理解成把a当作“高位”b当作“低位”用 7 进制的方式拼成一个整数。具体来说当a1时num取 1 到 7当a2时num取 8 到 14依此类推每一个从 1 到 49 的整数都恰好对应一个唯一的(a, b)组合。这和“骰子掷出点数组合”是一个道理。49 种组合等概率等于你有 49 张编号 1 到 49 的卡牌随便抽一张。现在目标是从 1 到 49 这 49 个等概率的数字中得到均匀的 1 到 10。有人说那我直接对 10 取模不就行了num % 10 1看起来能覆盖 1 到 10但注意 49 和 10 不是倍数关系取模之后不同余数对应的原始数字个数不一样结果一定不均匀。这一点后面会专门讲。既然 49 不能被 10 整除那就必须丢掉一部分结果。丢掉谁、怎么丢就引出了拒绝采样的核心思想。2. 基础解法两次 Rand7() 加拒绝采样2.1 Python3 代码与逐行解释最简单的解法是这样def rand10(): while True: num (rand7() - 1) * 7 rand7() # 均匀生成 1..49 if num 40: return (num - 1) % 10 1逐行解释一下(rand7() - 1) * 7 rand7()生成 1 到 49 的均匀整数。为什么均匀因为每个(a, b)组合概率相同而num和组合是一一对应的。判断num 40。为什么取 40因为 40 是 10 的倍数1 到 40 可以均匀地分成 10 组每组 4 个数字。数字 1 到 10 各出现 4 次。(num - 1) % 10 1把 1 到 40 均匀映射到 1 到 10。比如num为 1、11、21、31 时都返回 1num为 2、12、22、32 时都返回 2依此类推。如果num落在 41 到 49 之间说明抽到了“无效卡牌”直接重新循环再试一次。这个算法核心就是拒绝采样。我可以打个比方你手里有一副 49 张的公平牌组只有抽到前 40 张才算数抽到后 9 张就洗牌重抽。重抽不会破坏公平性因为每一次抽取都是独立且等概率的抽中“有效区域”的条件概率在每一轮完全相同所以最终返回的每个结果仍然是均匀的。2.2 期望调用次数的计算写题的时候经常会被问到“这个算法平均要调用多少次 rand7()”。这也是面试官喜欢追问的点。我们每次循环调用 2 次rand7()成功概率是 40/49。于是从循环次数来看期望循环次数是成功概率的倒数期望循环次数 1 / (40/49) 49/40所以期望调用rand7()的次数就是期望调用次数 2 × 49/40 49/20 2.45也就是说平均每生成一个 1 到 10 的结果大约要调用 2.45 次rand7()。这个数字不是每次固定的但如果你跑一百万次测试统计出来的平均值会非常接近 2.45。基础解法最大的优点是简单、容易解释清楚。只要能说清楚“为什么要拒绝 41 到 49”这个解法在面试里已经算合格了。但我自己刷题的时候总觉得那 9 个被丢掉的结果有点可惜毕竟它们本身也是等概率的于是又去研究了优化方案。3. 优化解法三段式拒绝采样3.1 拒绝掉的 9 种结果其实还能用基础解法丢掉 41 到 49 这 9 个数字但如果换个角度想当num落在 41 到 49 之间时num - 40得到的是 1 到 9这其实是一个均匀的rand9()。丢掉它等于把一个现成的rand9()扔了。那能不能把这个rand9()再和一次新的rand7()结合生成更大范围的均匀数字当然可以。rand9()和rand7()组合一共是 9×763 种等概率结果。63 比 10 大多了至少能取 60 个也就是 10 的倍数然后保留 3 个继续利用。再看如果第二轮也失败num - 60得到的是 1 到 3这又是一个均匀的rand3()。rand3()和rand7()组合一共是 3×721 种等概率结果取前 20 个正好又是 10 的倍数只剩 1 个无效结果需要重来。这就是三段式拒绝采样的思路每一层失败后不直接重来而是把失败分支的“残余均匀性”榨干一直用到实在榨不出来为止。3.2 Python3 优化代码代码如下def rand10(): while True: a rand7() b rand7() num (a - 1) * 7 b # 1..49 if num 40: return (num - 1) % 10 1 a num - 40 # 1..9等价于 rand9() b rand7() num (a - 1) * 7 b # 1..63 if num 60: return (num - 1) % 10 1 a num - 60 # 1..3等价于 rand3() b rand7() num (a - 1) * 7 b # 1..21 if num 20: return (num - 1) % 10 1这段代码里每一层的num都是均匀的关键在于a的取值始终是连续等概率的第一层若失败num是 41 到 49 均匀a num - 40就是 1 到 9 均匀。第二层a有 9 种可能b有 7 种可能组合出来的num (a-1)*7 b覆盖 1 到 63每个数恰好出现一次均匀。第二层若失败num只可能是 61、62、63对应的a num - 60是 1、2、3均匀。第三层a有 3 种可能b有 7 种可能组合出来 1 到 21 均匀取前 20 个映射最后一个失败后重新开始整个循环。整个过程的核心就是组合生成均匀整数截取“10 的整数倍”部分剩余部分再组合、再截取。3.3 期望调用次数从 2.45 次降到 2.1933 次优化版到底优化了多少我们需要算一下期望调用次数。设总期望调用次数为 E从第一层开始看第一层要调用 2 次rand7()。成功概率 40/49失败概率 9/49。如果失败进入第二层这时要额外调用 1 次rand7()。第二层成功概率 60/6320/21失败概率 3/631/21。如果第二层也失败进入第三层额外调用 1 次rand7()。第三层成功概率 20/21失败概率 1/21。如果第三层也失败就回到第一层重新来期望仍然是 E。于是可以列出递推方程E 2 (9/49) × [1 (1/21) × (1 (1/21) × E)]解得E 329/150 ≈ 2.1933对比基础版的 2.45优化版平均每次能省大约 0.26 次调用大概 10% 的收益。这个优化在 LeetCode 的测试用例上不会有明显感觉毕竟单次调用本身很快但如果你在做随机采样类的高频场景比如跑蒙特卡洛模拟、随机抽样生成这个差别就会被放大。注意优化版代码更长面试时一定要先讲清楚“每一层为什么是均匀的”再写代码。如果代码写出来了但解释不清楚均匀性面试官很可能会认为你是背的答案。4. 常见错误写法与均匀性证明4.1 两个典型错误写法的反例很多人第一反应是(rand7() rand7()) % 10 1这个写法看起来像模像样但均匀性一验证就崩。关键问题是两个rand7()的和并不是均匀分布。设s a b取值范围是 2 到 14。不同和值对应的组合数完全不同和值 s组合数2132435465768796105114123132141也就是说和为 8 的组合有 7 种和为 2 的组合只有 1 种。对这样的和值取模再 1不同输出值背后的组合数也必然不一样怎么可能均匀另一个常见错误是(rand7() * rand7()) % 10 1。乘法分布同样不是均匀的。比如乘积为 1 的情况只有(1,1)一种乘积为 2 的情况有(1,2)和(2,1)两种乘积为 4 的情况有(1,4)、(4,1)、(2,2)三种。取模之后每个余数对应的组合数也不相等。遇到这类写法最简单的验证办法是写个循环跑几十万次统计每个结果的频率一眼就能看出不均匀。这里我额外强调一点均匀性的本质是“每个输出值对应的原始组合数相同”。只要这一点不满足不管代码多简单、多直观它都是错的。4.2 如何严格证明输出是均匀的面试里被问到“怎么证明你的解法是均匀的”不要只说“显然均匀”。给出一个严谨一点的说法。以基础版为例。在返回结果之前程序实际上只会在1..49中截取1..40部分。num的 40 个值里每一个值出现的概率都是 1/49。映射时1 到 10 每个目标值对应 4 个不同num。所以条件在“本轮回合并成功返回”的情况下返回任意目标值 k 的概率都是 4/401/10。然后要处理“可能经过多轮才成功”的情况。每一轮的成功概率和条件分布完全一样失败的轮次只是重试不影响最终分布。所以整体来看返回任意目标值 k 的概率仍然等于 1/10。优化版的证明也同理。第一层返回时是从1..40均匀截取第二层返回时是从1..60均匀截取第三层返回时是从1..20均匀截取。每一层中任意目标值 k 对应的原始数字个数分别是 4、6、2而各自的总有效数字个数分别是 40、60、20条件概率都等于 1/10。各层之间互斥最终无条件概率自然也是 1/10。4.3 扩展任意 RandM() 构造 RandN() 的通用框架这类题目不只是考rand7()到rand10()稍微变形就成了一道新题但底层框架是通用的。如果 M ≥ N直接用拒绝采样先生成randM()取randM() ≤ N * (M // N)的部分映射到 1 到 N超出就重试。如果 M N先组合多次randM()构造一个更大的均匀整数空间使得M^k ≥ N。比如rand5()构造rand7()可以调用两次rand5()得到 25 种等概率结果取其中 21 个映射到 1 到 7剩下 4 个重试。如果空间非常大还可以像优化版那样把“剩余部分”递归利用减少重试次数。这里面有个有趣的延伸视角从信息论看rand7()每次携带约 log2(7) ≈ 2.807 bit 信息量而rand10()需要 log2(10) ≈ 3.322 bit所以理论上平均至少需要约 1.18 次rand7()才能生成一次rand10()。基础解法 2.45 次离理论下界还很远三段式优化 2.19 次已经进步了一些但依然不是最优。算法界有更复杂的方法能逼近理论下界只是面试和实际工程里很少需要那么极限的优化。5. 面试实战与刷题体会5.1 面试场上怎么答最加分实际面试时我不太建议一上来就甩优化代码。更稳的节奏是第一步先说思路。明确要构造等概率的大空间再说“因为 49 不是 10 的倍数所以要拒绝采样”。这句话能直接点出重点。第二步给基础版代码。一边写一边解释(rand7()-1)*7 rand7()为什么均匀以及为什么取 40。这个阶段如果能顺口说出期望调用次数49/20 ≈ 2.45基本就能让面试官满意。第三步如果面试官追问“能优化吗”再给出三段式版本。这时一定要先讲“拒绝掉的 9 个数并不是废料它们组成了一个均匀的 rand9()”把递推方程写出来、算出 2.1933 的期望。这属于明显的加分项。我自己当时在面试里碰到过类似题面试官其实不一定期待你写出优化版他更想确认你有没有真正理解均匀性和拒绝采样的原理。所以我建议优先保证基础版说得无懈可击再谈优化。5.2 一些个人习惯写这道题的时候有几个习惯我建议直接养成。第一写完算法题先验证分布。不要只盯着正确性还要随机跑一大轮统计频率。我用过的简单办法就是collections.Counter(rand10() for _ in range(100000))看一眼每个数字的计数是否接近 10000。如果某个数字明显偏多或偏少多半是映射逻辑出了问题。第二代码里不要硬编码魔法数字至少要写清楚每个数字的含义。比如 40 是7*7 - 960 是9*7 - 321 是3*7。写注释的时候把“为什么 40、60、20”标注清楚回头再看代码时不容易懵。第三这类题目的核心其实是“把两个独立均匀样本组合成一个更大的均匀样本”。一旦掌握了这个套路遇到rand3()生成rand5()、rand5()生成rand7()之类的变体都可以直接套框架而不是靠背答案。最后再说一个小技巧如果面试官要求“不允许无限循环”可以在代码里设置最大重试次数比如循环 100 次后强制返回一个兜底结果。虽然理论上有极小概率走到兜底但在工程上能避免极端情况下的死循环。当然LeetCode 原题没有这个限制直接while True就行。