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

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

例如,在列表中 [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?或者有一个单独的算法可以用来选择一个元素与它的重量成反比?