C++如何在多组给定区间中等概率生成符合要求的随机数

核心思路 #

要保证所有符合要求的数值被选中概率相等，不能直接平均选每个区间（因为不同区间长度不一样，短区间里的数会被抽中概率更高），正确的做法是按每个区间的数值总个数加权随机选择区间，再在选中的区间内随机取值。

具体步骤 #

• 第一步：预处理所有区间，统计每个区间包含的数值个数，以及所有区间的总数值个数
  对单个区间[a,b]，如果是左闭右开区间，数值个数是b - a，按你写的单区间生成代码来看，你用的就是左闭右开逻辑，直接按这个规则计算即可。
  比如示例里的三个区间：[23,28]长度5，[11,14]长度3，[31,39]长度8，总长度是16，每个数被选中的概率就是1/16。
• 第二步：加权随机选区间
  生成一个0到总长度之间的随机数，遍历区间累加长度，直到累加值大于这个随机数，对应的区间就是选中的区间。
  比如示例总长度16，生成随机数如果是6，前两个区间累加是5+3=8>6，就选第二个区间[11,14]。
• 第三步：在选中的区间内用你已有的单区间随机数代码生成数值即可。

示例代码（C++） #

#include <iostream>
#include <vector>
#include <utility>
#include <cstdlib>
#include <ctime>

int getRandomFromIntervals(const std::vector<std::pair<int, int>>& p) {
    // 计算所有区间总长度
    int total = 0;
    for (auto& interval : p) {
        total += interval.second - interval.first;
    }
    // 加权随机选择区间
    int r = rand() % total;
    int sum = 0;
    int selected_idx = 0;
    for (int i = 0; i < p.size(); i++) {
        int len = p[i].second - p[i].first;
        if (r < sum + len) {
            selected_idx = i;
            break;
        }
        sum += len;
    }
    // 选中区间内生成随机数
    return (rand() % (p[selected_idx].second - p[selected_idx].first)) + p[selected_idx].first;
}

int main() {
    srand(time(0)); // 随机种子全局初始化一次即可
    std::vector<std::pair<int, int>> p = {{23,28}, {11,14}, {31,39}};
    std::cout << getRandomFromIntervals(p) << std::endl;
    return 0;
}

注意事项 #

• 如果区间存在重叠，该方案依然成立，重叠部分的数值会因为属于多个区间，被选中的概率自动叠加，刚好符合所有数值等概率的要求。
• 如果你需要处理闭区间（比如[23,28]要包含28），把所有计算长度的地方改成interval.second - interval.first + 1，单区间生成代码也要对应改成rand() % (len + 1) + first即可。

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