怎样按概率产生随机数？

Question

请教一个问题：已知一个数组（N个元素），其中每个数对应一个权值，怎样在该数组中随机选择M（M<N）个元素，但是要使权值更大的元素有更大的概率被选中，应该怎样考虑呢？

Answer 1

举个例子：
数字 权值
1    5%
2    15%
3    30%
4    50%随机产生一个0到1的小数
if随机数<=0.05 就取1
else if 随机数>0.05 && 随机数<=0.05+0.15 就取2
依此类推

Answer 2

根据权值计算出每个数相应的概率，如Qi/(Q1+Q2+..+Qn)
然后寻找方法使得随机结果按这个概率分布

Answer 3

按6楼的办法得出概率0
然后求1/p
比如是13/29
那你就判断(random()*29)<13

Answer 4

也就说是判断 生成的随机数是否 < 1/p？
为什么呢？

Answer 5

弄的复杂了..
其实就是小于p...
因为随机函数都是[0,1)范围的...
小于p(0<p<1)的概率刚好就是p...

Answer 6

参考各位的方法，能否这样：
1 计算每个数对应的概率：Pi=Qi/(Q1+Q2+…+Qn)（由于权值Qi是降序排列，Pi也是降序排列）
2 取[0，1]之间随机数rand
3 判断rand在哪个区间：
  [0，P1]
  (P1,P1+P2]
  (P1+P2,P1+P2+P3]
   …
   (P1+P2+…Pn-1，1]
4 rand在哪个区间则取相对应的数

Answer 7

int[] map =
{
    1, // 1
    2,2,2,2, // 4
    3,3,3,3,3,3,3,3,3, // 9
    ......
};int n = 1 + 4 + 9 + 16 + 25 + 36 + 49 + 64 + 81 + 100;Random r = new Random();return map[r.nextInt(n)];