约束条件下生成符合升序要求的离散随机数方案求助

解决方案 #

我们提供两种可直接落地的实现，适配不同的使用场景： #

方案1：动态规划加权采样（近似均匀，性能最优） #

该方案从后往前计算每个位置取对应值时后续合法组合的总数，按总数加权采样，最大程度接近均匀分布，不会出现逐位生成导致的尾部位移问题。

实现逻辑

1. 提前对每个X[i]的取值空间做排序预处理
2. 从最后一位开始倒序计算每个候选值对应的合法组合计数
3. 从第一位开始，根据每个候选值的权重（对应后续合法组合数）随机抽取，保证每个合法样本被选中的概率近似相等

Python 代码实现

import bisect
import random
from typing import List

def non_decreasing_sample(sets: List[List[int]]) -> List[int]:
    # 预处理：每个取值集合排序，方便后续二分查找
    sorted_sets = [sorted(s) for s in sets]
    n = len(sorted_sets)
    # dp[i][j] 代表第i个位置取sorted_sets[i][j]时，后续所有位置的合法组合总数
    dp: List[List[int]] = [[] for _ in range(n)]
    
    # 最后一位的dp默认全为1，后方无其他元素约束
    dp[-1] = [1] * len(sorted_sets[-1])
    
    # 倒序计算每个位置的dp值
    for i in range(n-2, -1, -1):
        current_set = sorted_sets[i]
        next_set = sorted_sets[i+1]
        next_dp = dp[i+1]
        # 预处理下一位dp的后缀和，降低计算复杂度
        suffix_sum = [0] * (len(next_dp) + 1)
        for j in range(len(next_dp)-1, -1, -1):
            suffix_sum[j] = suffix_sum[j+1] + next_dp[j]
        # 计算当前位每个候选值对应的组合数
        for j in range(len(current_set)):
            val = current_set[j]
            # 查找下一位集合中第一个大于等于当前值的下标
            pos = bisect.bisect_left(next_set, val)
            dp[i].append(suffix_sum[pos])
    
    # 按权重采样生成结果
    res = []
    prev_val = -float('inf')
    for i in range(n):
        current_set = sorted_sets[i]
        current_dp = dp[i]
        # 过滤出满足大于等于上一位取值的候选
        pos = bisect.bisect_left(current_set, prev_val)
        candidates = current_set[pos:]
        weights = current_dp[pos:]
        # 加权随机选择当前位取值
        selected = random.choices(candidates, weights=weights, k=1)[0]
        res.append(selected)
        prev_val = selected
    return res

测试示例

# 代入问题中的示例验证
s1 = list(range(8, 32))
s2 = [10, 20, 30, 50]
s3 = list(range(1995, 2004))
print(non_decreasing_sample([s1, s2, s3]))
# 输出示例：[16, 20, 1999]

方案2：拒绝采样（完全均匀，适合n小、合法组合占比高的场景） #

如果对均匀性要求极高，且n≤10、合法组合占比不低于1%的场景可以使用该方案，逻辑简单无偏差，只要采样到不满足非降的结果就丢弃重抽。

Python 代码实现

import random
from typing import List

def rejection_sample(sets: List[List[int]]) -> List[int]:
    while True:
        # 每个位置独立随机抽取
        sample = [random.choice(s) for s in sets]
        # 校验是否满足非降约束
        valid = True
        for i in range(1, len(sample)):
            if sample[i] < sample[i-1]:
                valid = False
                break
        if valid:
            return sample

选型建议 #

• 合法组合占比不低于1%的场景优先选方案2，逻辑简单且完全均匀
• 合法组合占比极低、性能要求高的场景选方案1，近似均匀无尾部偏移
• 对于n≤40的场景，方案1时间复杂度为O(n*m log m)（m为单个取值空间的最大规模），即使m达到百万级也可正常运行

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