常常有这样的功能需求: 每次从一批候选项中随机选取其中一项, 要求每一项的出现都有一定的概率. 比如说, 有如下候选项和对应的概率: 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){
// 选中了
}
}
Loading ...
虽然原理和简单
我也实现了一个类似的功能：
http://blog.wangzhong.me/unequal-probability-random-selection-algorithm-to-achieve-weightedrandom-php.html Reply
不过，把概率转换成相应的整数来简化计算却不太合理。因为，有些概率是0.15这样的，有些概率可能确实0.012345678这样的。当然，可以同时扩大1000000000倍，但如果不能表示那么长的数呢？当然，也可以将小数的位数进行舍取，难免会失去精度的。
不过，本文的实现方法在工程上是很合理的。 Reply