代码之家 › 专栏 › 技术社区 › Danny Sullivan

基于反权重从列表中选择随机元素

algorithm

Danny Sullivan · 技术社区 · 6 年前

我有一个加权元素列表,我想选择一个具有概率的元素 相反地 与它的重量成比例。

例如,在列表中 [a, b, c] 带权 [4, 3, 2] 分别地,我可以使用加权概率消除元素,直到我有一个1个元素的列表,这是所选的元素。在这个算法中,在第一次迭代中,元素 a 可能会被淘汰 4/9 . 如果 一 在第一轮就被淘汰了,我们有一个阵型 [b, c] 带权 [3, 2] . 从那里开始,元素 b 可能会被淘汰 3/5 . 如果 乙 被排除,我们选择了元素 c .

在有3个元素的情况下, C 被选中的概率是 一 和 乙 被淘汰。这和 一 然后 乙 加上 乙 然后 一 被淘汰或

(
    // a eliminated first
    w(a) / (w(a) + w(b) + w(c)) *
    // b eliminated second
    w(b) / (w(b) + w(c))
) +
(
    // b eliminated first
    w(b) / (w(a) + w(b) + w(c)) *
    // a eliminated second
    w(a) / (w(a) + w(c))
)

有没有一种方法可以快速计算每个元素的概率,而不考虑列表中元素的数量,并确认概率总和为1?或者有一个单独的算法可以用来选择一个元素与它的重量成反比?

1 回复 | 直到 6 年前

k_ssb 6 年前

以与某些权重成反比的概率抽样,可以等效地以概率与这些权重的倒数成比例地进行抽样。因此,我们首先反转所有的权重,将权重标准化,使其总和为1(形成概率分布),然后从该分布中正常采样。

下面是一些python风格的伪代码:

weights = [1.0 / w for w in weights]           # Invert all weights
sum_weights = sum(weights)
weights = [w / sum_weights for w in weights]   # Normalize weights
return numpy.random.choice(options, p=weights) # Sample

或在麻木中:

weights = numpy.reciprocal(weights)            # Invert all weights
weights = weights / numpy.sum(weights)         # Normalize
return numpy.random.choice(options, p=weights) # Sample

推荐文章

SkyWalker · 在JavaScript中,合并日期-时间序列的有效算法是什么?

1 年前

root · 计数算法

1 年前

André Silveira · 使用循环将数组的每个槽递增1。数组的大小是传递给函数的参数

2 年前

danial · 如何在多个字符串的每个位置找到最频繁的字符

2 年前

Manny · 如何比较Perl中的字符串?

2 年前

Suhail Gupta · 在排序阵列中查找目标范围的时间复杂度-此解在最坏情况下是否为O(N)?

2 年前

Diret · 获取范围内每个数字的子倍数的算法

2 年前

Saif · 排序时python如何决定何时调用比较器?

2 年前

TryingToLearn · 我如何为通用遥控器构造一个类,该遥控器向连接到它的各种设备发送开/关命令?

2 年前

Sneha Sharma · 滑动窗口-在我的代码中找不到错误(非常基本的算法)

2 年前