我正在寻找一种算法(无论什么编程语言,也许是伪代码?),您可以在其中获得具有不同概率的随机数。
例如:
A random Generator, which simulates a dice where the chance for a '6' is 50% and for the other 5 numbers it's 10%.
该算法应该是可扩展的,因为这正是我的问题:
I have a array (or database) of elements, from which i want to select 1 random element. But each element should have a different probability to be selected. So my idea is that every element get a number. And this number divided by the sum of all numbers results the chance for the number to be randomly selected.
有人知道解决这个问题的好编程语言(或库)吗? 最好的解决方案是一个好的 SQL 查询,它提供 1 个随机条目。 但我也会对其他编程语言的每一个提示或尝试感到高兴。
最佳答案
实现它的一个简单算法是:
- 创建一个辅助数组,其中
sum[i] = p1 + p2 + ... + pi
。此操作仅执行一次。 - 当你画一个数字时,画一个在
[0,sum[n])
上均匀分布的数字r
,并二分查找第一个数字高于均匀分布的随机数。可以使用 binary search 来完成高效。
很容易看出,r
确实位于某个范围[sum[i-1],sum[i])
的概率,确实是sum[i]-sum[i-1] = pi
(在上面,为了完整性,我们认为sum[-1]=0
)
对于您的立方体示例:
你有:
p1=p2=....=p5 = 0.1
p6 = 0.5
首先,计算sum
数组:
sum[1] = 0.1
sum[2] = 0.2
sum[3] = 0.3
sum[4] = 0.4
sum[5] = 0.5
sum[6] = 1
然后,每次需要抽数字时:在[0,1)
中抽一个随机数r
,并选择最接近它的数字,例如:
r1 = 0.45 -> element = 4
r2 = 0.8 -> element = 6
r3 = 0.1 -> element = 2
r4 = 0.09 -> element = 1
关于algorithm - 概率可调的随机算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30756067/