如何高效采样长度为l且至少包含k个1的随机0-1序列

我们默认需求是均匀采样，即所有满足条件的序列被抽中的概率完全相等，以下是不同场景下的可行方案：

通用无拒绝采样方案（全场景适用，k接近l时也无性能损耗） #

这个方案完全不需要丢弃无效样本，无论k和l的比例如何都能稳定运行，核心思路是先按权重抽样1的实际个数，再抽样对应数量1的序列：

• 第一步：计算每个合法1的个数的概率权重：长度为l的序列中恰好有m个1的序列总数为组合数C(l, m)，因此满足m≥k的所有m对应的权重就是C(l, m)，总权重为所有合法权重的和S = sum_{m=k}^l C(l, m)
• 第二步：按权重比例随机抽取一个合法的m值：生成[0, S)区间内的均匀随机数，找到最小的m使得sum_{t=k}^m C(l, t) > 随机数，即为本次要采样的1的个数
• 第三步：均匀采样恰好有m个1的长度为l的0-1序列：可以用经典的随机抽样算法，直接从l个位置中不放回抽m个位置设为1，其余设为0即可，该步骤时间复杂度为O(l)

示例实现（Python） #

import random
import math

def sample_valid_binary_seq(length: int, min_one_count: int) -> list[int]:
    # 边界处理：k=0直接返回全随机序列，k=l直接返回全1序列
    if min_one_count == 0:
        return [random.randint(0,1) for _ in range(length)]
    if min_one_count == length:
        return [1]*length
    
    # 计算各合法m的权重
    weights = [math.comb(length, m) for m in range(min_one_count, length+1)]
    total_weight = sum(weights)
    # 按权重抽样m
    r = random.randint(0, total_weight - 1)
    cum_weight = 0
    selected_m = min_one_count
    for idx, w in enumerate(weights):
        cum_weight += w
        if cum_weight > r:
            selected_m = min_one_count + idx
            break
    # 抽样对应m个1的序列
    one_positions = random.sample(range(length), selected_m)
    res = [0]*length
    for pos in one_positions:
        res[pos] = 1
    return res

优化版拒绝采样（适合k或l-k较小的场景） #

朴素拒绝采样在k接近l时接受率极低，性能会大幅下降，可以做两个方向的优化：

• 提前终止：生成序列时边生成边统计已出现的1的个数，如果剩余位置全填1也达不到k的要求，直接终止当前生成流程，无需补完剩余位
• 等价转换：如果k非常接近l，说明l-k很小，可以把原问题等价为「采样至多有l-k个0的序列」，反过来对0做拒绝采样，接受率会大幅提升

当k远小于l/2时，朴素拒绝采样的接受率已经足够高，不需要额外优化即可满足需求。

内容的提问来源于stack exchange，提问作者Vezen BU