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