从数组中加权随机选择?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (37)

我想从数组中随机选择一个元素,但每个元素都有已知的选择概率。

所有概率(在数组内)总和为1。

什么算法是最快和最适合巨大计算的?

例:

id => chance
array[
    0 => 0.8
    1 => 0.2
]

对于这个伪代码,所讨论的算法应该在多个调用中统计地返回id 0上一个元素的id 上的四个元素1

提问于
用户回答回答于

计算列表的离散累积密度函数(CDF)或者以简单的方式计算权重的累积和数组。然后生成一个介于0和所有权重之和(在你的情况下可能是1)的范围内的随机数,在二进制搜索中找到离散CDF数组中的这个随机数,并获得与此条目相对应的值,这是你的加权随机数。

用户回答回答于
rand_no = rand(0,1)
for each element in array 
     if(rand_num < element.probablity)
          select and break
     rand_num = rand_num - element.probability

所属标签

可能回答问题的人

  • 天使的炫翼

    15 粉丝531 提问35 回答
  • 富有想象力的人

    2 粉丝0 提问26 回答
  • 旺仔小小鹿

    社区 · 运营 (已认证)

    48 粉丝0 提问26 回答
  • 发条丶魔灵1

    6 粉丝525 提问25 回答

扫码关注云+社区

领取腾讯云代金券