algorithm - 概率可调的随机算法

Question

我正在寻找一种算法(无论是什么编程语言，也许是伪代码？)，您可以在其中获得具有不同概率的随机数。

例如:

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.

有人知道解决这个问题的好的编程语言(或库)吗？最好的解决方案是提供 1 个随机条目的良好 SQL 查询。但我也会对其他编程语言的每一次提示或尝试感到满意。

Answer 1

实现它的一个简单算法是:

1. 创建一个辅助数组，其中 sum[i] = p1 + p2 + ... + pi。这只进行一次。
2. 当你画一个数的时候，画一个在[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