例如,我想从集合S ={0,1,2,3}中获取随机数。但不是每个数字都有相同的概率(25%)现在每个数字有不同的概率,比如{50%,30%,20%,10%}。我该如何编码呢?Java或c#(我更喜欢c#)。
Alias方法是目前为止我最喜欢的方法。
http://code.activestate.com/recipes/576564-walkers-alias-method-for-random-objects-with-diffe/我没有看过这段代码,但它是一个顶级的谷歌结果。
这是另一个更好的解释
http://pandasthumb.org/archives/2012/08/lab-notes-the-a.html实际上我在面试中经常用这个问题,因为如果你从来没有见过这个问题,它可能会让你很困惑。
如果上面的代码对你来说太难实现了,还有一个更简单的输入循环解决方案。
使用PHP,因为它更容易显示代码。
function getNumberFromDistribution($dist) {
$totalProbability = 0;
$randomNumber = mt_rand(0, mt_getrandmax()) / mt_getrandmax(); //uniform random number between 0-1
foreach($dist as $number => $chance) {
if (($totalProbability += $chance) <= $randomNumber) {
return $number;
}
}
return null; //only reachable on bad input
}
如果集合很小,您可以构建一个数组,其中包含获得分布所需的每个值的正确数量。得到1的概率是得到3的概率的3倍。然后,您将使用数组的长度来确定用作索引的随机数。