2011-08-03

概率选取的实现

Views: 10926 | 5 Comments

常常有这样的功能需求: 每次从一批候选项中随机选取其中一项, 要求每一项的出现都有一定的概率. 比如说, 有如下候选项和对应的概率: A:10%, B:5%, C:25%, D:60%.

现在, 把每一项的概率用一个正整数(概率值)来表示, 不使用百分率, 整数的总和不一定等于100, 可以是任意大小,

实际概率 = 概率值/总和 * 100%

概率选取的算法如下:

  • 依次(顺序可随机)将各项按概率值从原点开始放在一维坐标上首尾相连, 这样, 每一项对应一个取值区间
  • 在总区间范围内随机选取一个点, 落在哪一项对应的区间就选中哪一项

用伪码表示:

total_p = sum(p1 + p2 + p3 + ...)
rand = random(1, total_p) // [1, total_p]
foreach(items as item){
    rand -= item.p
    if(rand <= 0){
        // 选中了
    }
}

Related posts:

  1. C++ STL 迭代器的失效原则
  2. 用PHP遍历SSDB中的zset集合
  3. 生产者消费者模型中生产者的速度快于消费者时所产生的问题及其解决方法讨论
  4. PHP中使用foreach和引用导致程序BUG
  5. 百行代码实现一个简单的Zset(SortedSet)
Posted by ideawu at 2011-08-03 09:02:49

5 Responses to "概率选取的实现"

Leave a Comment