约 13 分钟5 张卡

随机算法

随机算法在执行中使用随机选择，但“调用了随机数函数”不等于结果满足目标分布。输入有多少种等概率情况、每个输出对应几种情况、遇到不合适的结果是否重试，都会改变最终概率。

准备这类题时，先把随机目标说清楚：是每个整数等概率，每个子集等概率，还是按权重分配？红包还要满足金额总和、最低金额和领取次数等约束。概率推导负责说明算法为什么正确，统计检查则帮助发现实现错误，两者不能互相替代。

1. 面试核心

先记住这几条，再读正文

均匀输入经过映射后，只有每个输出对应的输入概率之和相同，才能保持均匀。直接取模可能让某些输出对应更多输入。卡 · 从 rand5 构造 rand3 与 rand8
拒绝采样丢弃不能均匀分配的输入后重试；需要说明接受概率和期望调用次数，不能把期望有限说成必定在固定次数内完成。卡 · 从 rand5 构造 rand3 与 rand8
从偏置 0/1 源提取等概率结果时，独立同分布且概率不退化是本文证明的前提。只知道一次输出的概率，不足以保证整段随机序列可用。卡 · 从偏置二值源提取公平结果
不放回抽样要区分输入能否修改、输出空间是否计入、结果是否需要随机顺序。原地交换与只读扫描可以满足不同条件。卡 · 允许修改数组
整数权重可以转成前缀区间，区间长度占总长度的比例就是选择概率；零权重、边界比较和总权重溢出都要检查。卡 · 整数权重采样
随机金额与随机领取资格是两个问题。金额守恒不证明分布公平，随机金额也不证明每个人的领取机会相同。卡 · 综合题

2. 随机源与目标分布

均匀分布表示目标集合中的每个结果具有相同概率。例如从 0、1、2 中均匀选择，每个值的概率是 1/3。独立表示知道此前结果，不会改变下一次结果的概率；每次单独看的输出概率相同，不等于这些输出独立。

本文用 randbelow(n) 表示从 [0,n) 均匀取一个整数，并在证明中假设需要的各次抽取独立。n 必须是正整数。范围端点是接口的一部分：[0,n) 有 n 个结果，[0,n] 则有 n+1 个。

示例使用 Python 3.12 的接口。random.Random 适合可重复的测试和模拟；若需要让外部参与者难以预测结果，应选用操作系统支持的安全随机源，例如 secrets.randbelow 或 random.SystemRandom。安全随机源解决不可预测性，不能修复算法本身的取模偏差，也不能代替领取资格和并发校验。

固定种子方便重放失败，但不应把“某个种子下看起来均匀”当成证明。复现还要保留运行版本、输入和随机调用顺序；改变一次调用，就可能改变后续全部结果。

3. 拒绝采样

卡 · 用 rand5 怎样构造等概率的 rand3 和 rand8？卡 · 一个偏置 0/1 随机函数，怎样变成等概率输出？

拒绝采样先从容易生成的分布中抽取候选，只接受满足条件的结果，其余重新抽取。对有限均匀输入，可以保留一个大小为目标结果数整数倍的区域，再做映射。

假设 rand5() 独立、等概率地产生 1—5。直接计算 (rand5()-1)%3+1，结果 1 和 2 各对应两个输入，结果 3 只对应一个输入，概率分别为 2/5、2/5、1/5，并不均匀。

3.1 从 rand5 构造 rand3 与 rand8

生成 1—3 时，可以只接受 1、2、3。接受后的三种值原本等概率，因此条件分布也相同。

生成 1—8 时，一次 rand5 不够。取两次结果 a、b，构造 (a-1)*5+(b-1)，得到 0—24 的 25 种等概率组合。只接受 0—23，再对 8 取模，每个结果都有三个原像，也就是三个能映射到它的输入值。

def rand3(rand5) -> int:
    while True:
        value = rand5()
        if value <= 3:
            return value


def rand8(rand5) -> int:
    while True:
        value = (rand5() - 1) * 5 + rand5() - 1
        if value < 24:
            return value % 8 + 1


source3 = iter([5, 4, 2])
source8 = iter([5, 5, 1, 4])
print(rand3(lambda: next(source3)))
print(rand8(lambda: next(source8)))

这段示例用预设序列重放拒绝过程，输出 2 和 4。rand3 先拒绝 5、4；rand8 先由 (5,5) 得到 24 并拒绝，再由 (1,4) 得到 3，映射成 4。预设序列只演示执行过程，不是均匀随机源，也不用于证明概率。

一次尝试的接受概率为 q 时，独立重试的期望尝试次数是 1/q。所以 rand3 期望调用 rand5 的次数为 5/3；rand8 每次尝试调用两次，期望总调用次数为 2×25/24=25/12。

接受概率大于零且各次尝试独立时，算法以概率 1 最终结束，但没有有限的最坏重试次数。若接口要求超时或尝试预算，耗尽后可以显式失败；不能悄悄返回某个固定值，否则会给这个值额外的概率。

3.2 从偏置二值源提取公平结果

假设 biased_bit() 每次独立地产生 0 或 1，产生 0 的概率始终为 p，且 0 < p < 1。成对读取时：

输入对	概率	处理
00	p²	拒绝
01	p(1-p)	返回 0
10	(1-p)p	返回 1
11	(1-p)²	拒绝

01 与 10 的概率相等，所以只保留这两种情况即可，不需要知道 p 的具体值：

def fair_bit(biased_bit) -> int:
    while True:
        a, b = biased_bit(), biased_bit()
        if a != b:
            return a


source = iter([0, 0, 1, 0])
print(fair_bit(lambda: next(source)))

输出 1：先拒绝 00，再接受 10。每对接受概率是 2p(1-p)，每个输出期望消耗 1/[p(1-p)] 次原始调用。p 越接近 0 或 1，平均等待越长；p 为 0 或 1 时，源根本没有可提取的随机性。

独立同分布是这里足够且清楚的前提，不能只省略成“原函数有偏”。例如先随机取一位，再永远重复它，各位置的 0/1 概率可以相同，但所有读取对都是 00 或 11，算法不会返回。如果不同位置的 p 不同，01 与 10 也未必等概率。

4. 不放回抽样

卡 · 从互异数组随机选 M 个不重复元素，怎样使用 O(1) 额外空间？卡 · 随机红包怎样同时满足金额约束与领取公平性？

不放回抽样选中一个位置后，不再选择它。对于含 N 个互异元素的数组，均匀选 M 个元素，通常是要求每个大小为 M 的子集概率相同；如果还要求输出顺序随机，则每个有序样本也要等概率。

O(1) 空间的要求需要说明是否排除输入和输出。返回一个新列表本身就要存 M 项；下面的 O(1) 指算法工作状态，不包含调用者要求保存的输出。

4.1 允许修改数组

部分 Fisher–Yates 洗牌只处理前 M 个位置。第 i 步从尚未选中的区间 [i,N) 均匀取一个位置，与 i 交换。这样每一步都从剩余元素中均匀选择，不会重复。

def choose_in_place(values: list[int], m: int, randbelow) -> None:
    if not 0 <= m <= len(values):
        raise ValueError("invalid sample size")
    for i in range(m):
        j = i + randbelow(len(values) - i)
        values[i], values[j] = values[j], values[i]


def choose_read_only(values, m: int, randbelow, emit) -> None:
    if not 0 <= m <= len(values):
        raise ValueError("invalid sample size")
    for i, value in enumerate(values):
        if m == 0:
            return
        remaining = len(values) - i
        if randbelow(remaining) < m:
            emit(value)
            m -= 1


from random import Random

rng = Random(101)
values = [0, 1, 2, 3, 4]
choose_in_place(values, 3, rng.randrange)
print(values[:3])
selected = []
choose_read_only(tuple(range(5)), 3, rng.randrange, selected.append)
print(selected)

在 CPython 3.12.13 中，这段程序输出 [4,2,0] 和 [0,2,3]。第一个函数完成后，values 的前 3 项是选中的元素；values[:3] 为了输出另建了一个列表，这个副本不属于原地算法的 O(1) 工作空间。第二个函数按原顺序输出三个不同位置的元素，不修改输入，selected 则是调用者保存的结果。

任意一个有序样本被选中的概率都是 1/[N(N-1)…(N-M+1)]。同一个无序子集对应 M! 种顺序，因此子集概率也是相同的。原地方法执行 M 次交换，若随机整数生成按常数成本计算，时间 O(M)、额外工作空间 O(1)。输入互异是题设前提，函数没有另建集合来检查。

4.2 输入只读

只读数组也能用 O(1) 工作空间抽样，但可以改为顺序扫描：还剩 R 个位置，需要选 K 个时，以 K/R 的概率选择当前位置。选中后 K 减一，不论是否选中都进入下一个位置。上一节的 choose_read_only 用 randbelow(R) < K 实现这个概率。

对任意目标子集，按它要求的位置作出“选或不选”的概率乘积为 M!(N-M)!/N!，因此所有子集等概率。剩余位置数等于需要数量时，后面的元素都会被选中，不会因运气不好而少选。

这种方法最多扫描 N 项，时间 O(N)、工作空间 O(1)，但输出保持原数组顺序。如果要求随机输出顺序，还需要增加洗牌等步骤。原题只说空间限制时，不应擅自补上“输入可修改”或“输出空间也必须为零”。

5. 整数权重采样

卡 · 怎样按整数权重抽样，零权重和累计边界怎样处理？

权重采样让第 i 项被选中的概率为 weight[i]/total，其中权重非负，总权重大于零。可以把每个权重看成该项拥有的整数票数，再从全部票中均匀抽一张。

对权重 [1,0,3]，累计边界是 [1,1,4]。票号 0 属于第 0 项，票号 1、2、3 属于第 2 项；第 1 项的区间长度为零，不能被选中。累计区间的构造与前缀和相同。

from bisect import bisect_right


def weight_prefix(weights: list[int]) -> list[int]:
    if not weights or any(type(w) is not int or w < 0 for w in weights):
        raise ValueError("weights must be nonnegative integers")
    prefix = []
    total = 0
    for weight in weights:
        total += weight
        prefix.append(total)
    if total == 0:
        raise ValueError("total weight must be positive")
    return prefix


def pick_weighted(prefix: list[int], randbelow) -> int:
    ticket = randbelow(prefix[-1])
    return bisect_right(prefix, ticket)


prefix = weight_prefix([1, 0, 3])
print([pick_weighted(prefix, lambda n, ticket=ticket: ticket) for ticket in range(4)])

输出 [0,2,2,2]，这是遍历全部四个票号的结果，不是一次抽样统计。bisect_right 找第一个严格大于票号的累计边界，恰好跳过零长度区间。换成 bisect_left 会把边界票号分给前面的区间，改变概率。

先花 O(N) 时间构建前缀表，之后一次选择用 O(log N) 次比较。pick_weighted 要求传入 weight_prefix 构建的有效前缀；权重变动后要同步重建或维护累计结构。Python 可以保存很大的整数总权重，固定宽度实现则必须检查求和溢出。用整数票数也避免了把巨大总权重先转成浮点数时的精度损失，但仍要保证随机源支持所需范围。

6. 金额分配与领取资格

卡 · 随机红包怎样同时满足金额约束与领取公平性？

红包设计至少要分清三个问题：总额怎样拆成若干金额，谁有资格领取，以及并发请求怎样确保只领取一次。三个问题使用的规则不同，不能把一个随机公式当成完整设计。

6.1 总额与分布

先用整数最小货币单位表示金额，例如“分”，避免在反复分配时积累浮点误差。设总额为 T 分、需要 N 份、每份至少 1 分，那么必须满足 T ≥ N ≥ 1。

一个明确的随机目标是：每一种有顺序的正整数拆分等概率。它可以通过切点实现：在 1 到 T−1 之间均匀选 N−1 个不同切点，排好序，相邻边界之差就是各份金额。

from random import Random


def split_cents(total: int, count: int, rng) -> list[int]:
    if type(total) is not int or type(count) is not int or not 1 <= count <= total:
        raise ValueError("require integer total >= count >= 1")
    cuts = sorted(rng.sample(range(1, total), count - 1))
    boundaries = [0, *cuts, total]
    return [boundaries[i + 1] - boundaries[i] for i in range(count)]


amounts = split_cents(10, 3, Random(101))
print(amounts)
print(sum(amounts), len(amounts), min(amounts) >= 1)

在 CPython 3.12.13 中，第一行输出 [4,2,4]，第二行输出 10 3 True。所有切点都在内部且互不重复，所以每份为正数，相邻差相加又恰好还原总额。每组切点唯一对应一种有顺序的拆分；如果切点子集均匀，拆分也均匀。这里用 random.sample 选切点，它会保存样本，因此这个金额示例不声称满足上一节的 O(1) 空间要求。

这个目标不代表“每个人拿到的每种金额都等概率”。例如 5 分拆 3 份共有 6 种正整数拆分，第一份为 1、2、3 分的概率分别是 3/6、2/6、1/6。各个位置拿到金额的概率分布相同，但单个位置的金额并不均匀。上限、最低金额、波动范围和领取顺序的要求改变后，需要重新设计分布，不能随手截断结果后仍声称均匀。

这是一个可解释、可验证的教学方案，不描述任何现有产品的内部红包算法。原题如果只要求“尽可能随机”，应先把可检验的公平目标约定下来。

6.2 谁能领取与结果重试

先到先得的接口并不保证每位参与者等概率：网络延迟、重试频率和并发上限都会影响机会。若目标是在一组已确定的合格参与者中等概率抽取获奖者，可以先固定候选集合，再做不放回抽样；若按权重分配机会，则使用明确的权重规则。动态报名、抽取时刻和重复身份也要有一致的定义。

领取状态应把请求标识、领取者和已分配金额一起持久化，并通过事务或原子状态转换防止重复消费同一份额。相同请求重试时返回原结果，不能再抽一个金额；否则重试会改变分布，也可能破坏总额守恒。具体的请求标识和恢复机制见分布式流程恢复。

7. 概率证明与验证

验证随机算法时，可以把检查分成三层：

层次	能检查什么	不能替代什么
概率推导	原像数量、条件概率、子集概率以及所需假设	不能保证代码忠实实现推导
小规模穷举	全部票号、输入组合、抽取路径与边界映射	有限规模不能覆盖所有输入
多次抽样观察	输出频次、重试次数和明显偏差	接近理论值不能证明均匀或不可预测

固定种子用于定位实现差异，可以再用多个种子观察稳定性。样本量有限时，频次本来就会波动；不能要求每个输出次数恰好相同，也不能因为一次结果相近就停止检查。

金额总和、无重复、输出范围、样本数量等不变量可以对每次执行严格断言。均匀性则先靠条件明确的推导，再用小规模精确枚举与统计观察相互核对。随机源失去独立性、权重全零、M 超过 N、重试预算耗尽等情况，要作为单独的边界处理。