怎样按概率产生随机数？

trilobiteh 2008-10-09 10:37:44

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

...全文

1009 15 打赏收藏转发到动态举报

写回复

用AI写文章

15 条回复

切换为时间正序

请发表友善的回复…

发表回复

luzhen328 2011-04-11

打赏
举报



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)];

如一宝宝 2011-04-11

打赏
举报

[Quote=引用 14 楼 luzhen328 的回复:]

Java code

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.nextI……
[/Quote]

trilobiteh 2008-10-09

打赏
举报

[Quote=引用 12 楼 chaircat 的回复:]
引用 11 楼 trilobiteh 的回复:
参考各位的方法，能否这样：
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在哪个区间则取相对应的数

就这样...
权值可以是乱序的..
[/Quote]

嗯，谢谢

chaircat 2008-10-09

打赏
举报

[Quote=引用 11 楼 trilobiteh 的回复:]
参考各位的方法，能否这样：
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在哪个区间则取相对应的数
[/Quote]
就这样...
权值可以是乱序的..

trilobiteh 2008-10-09

打赏
举报

参考各位的方法，能否这样：
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在哪个区间则取相对应的数

chaircat 2008-10-09

打赏
举报

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

trilobiteh 2008-10-09

打赏
举报

[Quote=引用 8 楼 chaircat 的回复:]
按6楼的办法得出概率0
然后求1/p
比如是13/29
那你就判断(random()*29) <13
[/Quote]

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

chaircat 2008-10-09

打赏
举报

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

trilobiteh 2008-10-09

打赏
举报

[Quote=引用 3 楼 chaircat 的回复:]
比如1/3概率
那就mod 3
[/Quote]

能解释一下吗？

paulmake 2008-10-09

打赏
举报

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

brallow 2008-10-09

打赏
举报

[Quote=引用 1 楼 copico 的回复:]
被选的数
1 2 3 4 5 6 7 8 9 10

权值后
1 4 9 16 25 36 49 64 81 100

然后从1-100中选择一个随机数
随机数是1 1被选中
随机数是2-4 2被选中
随机数是5-9 3被选中
...
随机数是82-100 10被选中

LZ这种思路可好?

[/Quote]
支持这套方案，其实也不一定要用100.
反正连续的累加权值直到最后一个数，即可。

止戈而立 2008-10-09

打赏
举报

[Quote=引用 1 楼 copico 的回复:]
被选的数
1 2 3 4 5 6 7 8 9 10

权值后
1 4 9 16 25 36 49 64 81 100

然后从1-100中选择一个随机数
随机数是1 1被选中
随机数是2-4 2被选中
随机数是5-9 3被选中
...
随机数是82-100 10被选中

LZ这种思路可好?
[/Quote]

我认为应该是在1至（所有权值之和）取一个随机数。
随机数是1 1被选中
随机数是1+1-1+4 2被选中
随机数是1+4+1-1+4+9 3被选中
……

chaircat 2008-10-09