嘿，这个问题我之前也碰到过——拒绝采样虽然逻辑简单，但要是目标k对应的概率和特别小，反复重试的效率真的拉垮。下面给你分享几种更高效的方法，每一种都有明确的理论支撑：

1. 顺序条件采样法 #

这是最实用的精确采样方法之一，核心思路是逐个元素做决策，每一步都基于「还需要选多少个」和「剩余元素」的条件概率，完全避免无效重试。

具体步骤：

• 初始化：剩余需要选的元素数 r = k，剩余待处理元素集合 S = [n]
• 遍历每个元素 i ∈ S（可以按顺序来，不用打乱）：
  1. 计算当前状态下选i的条件概率：
     $q_i = \frac{p_i \cdot P(r-1, S\setminus{i})}{P(r, S)}$
     这里的 $P(t, T)$ 表示从集合T中选t个元素的伯努利概率和（也就是集合T对应的Poisson二项分布在t点的概率值）。
  2. 做一次伯努利试验：以概率q_i选择是否把i加入目标子集X。
  3. 如果选了i，就把r减1；如果没选，就跳过。
  4. 当r = 0时，剩下的所有元素都直接跳过；当剩余元素数等于r时，把剩下的元素全部加入X。

理论依据：每一步的条件概率严格符合目标分布的边际特性。我们始终在「最终恰好选k个元素」的条件下做决策，通过动态更新剩余需求和剩余元素的概率和，保证每一步的选择都和目标分布的联合概率一致，最终得到的子集完全符合要求的概率分布。

2. 预处理Poisson二项分布的贪心构建法 #

如果n比较小（比如n ≤ 50），可以先预处理Poisson二项分布的相关值，再贪心构建子集，效率很高。

具体步骤：

• 预处理阶段：
  1. 计算整个集合[n]的Poisson二项分布值P(m)（m从0到n），也就是所有大小为m的子集的概率和。
  2. 对每个元素i，计算P_i(k)：所有包含i的k子集的概率和，这个可以用递推式快速得到：$P_i(k) = p_i \cdot P_{-i}(k-1)$，其中P_{-i}(t)是去掉元素i后剩余集合的Poisson二项分布在t点的概率。
• 构建子集阶段：
  1. 对当前剩余元素集合和剩余需要选的数量t，计算每个元素i被选入的概率为$\frac{P_i(t)}{P(t)}$（这里的P(t)是当前剩余集合的t子集概率和）。
  2. 按这个概率选择是否把i加入X：如果选了，就从剩余集合中去掉i，t减1；如果没选，就只去掉i，t不变。
  3. 重复直到t = 0或者剩余元素数等于t。

理论依据：这是基于概率的链式法则，每一步的选择都严格对应目标分布的边际概率。预处理的Poisson二项分布值让我们可以快速计算每一步的条件概率，整个过程没有无效采样，每一步都在向目标子集推进。

3. 大n场景下的近似采样法 #

当n非常大时，精确计算Poisson二项分布的成本太高，这时候可以用近似方法在保证精度的前提下提升效率：

• 首先用正态分布近似Poisson二项分布：Poisson二项分布的均值$\mu = \sum_{i=1}^n p_i$，方差$\sigma^2 = \sum_{i=1}^n p_i(1-p_i)$，当n足够大时，P(k)可以用正态分布$N(\mu, \sigma^2)$在k附近的概率值近似。
• 然后用顺序重要性采样（SIS）：先按独立伯努利分布采样一批候选子集，给每个k子集分配权重$\frac{\Pr[X]}{P(k)}$，再按权重对这些k子集进行重采样，得到最终的样本。

理论依据：中心极限定理保证了正态近似的合理性，当n足够大时，近似误差可以控制在很小的范围内。顺序重要性采样通过加权修正采样偏差，避免了拒绝采样的无效尝试，在大n场景下效率远超拒绝采样。

适用场景总结 #

• 顺序条件采样：适合n中等、k灵活变化的场景，可通过递推优化P(r,S)的计算，避免重复计算Poisson二项分布。
• 预处理Poisson二项分布法：适合n较小的场景，预处理成本可控，采样过程完全精确。
• 近似采样法：适合n很大、对精度要求不是极端严格的场景，平衡了效率和精度。

备注：内容来源于stack exchange，提问作者Vezen BU