从元素具有权重的列表中选择k个随机元素

Question

从元素具有权重的列表中选择k个随机元素这里精美地描述了没有任何权重（相等概率）的选择。我想知道是否有办法将这种方法转换为加权方法。我也对其他方法感兴趣。更新：无需更换的采样

Answer 1

我知道这是一个非常古老的问题，但是如果你应用一点数学，我认为在O（n）时间有一个巧妙的技巧！

该指数分布有两个非常有用的特性。

1. 给定来自具有不同速率参数的不同指数分布的n个样本，给定样本的最小概率等于其速率参数除以所有速率参数的总和。

2. 它是“无记忆的”。因此，如果您已经知道最小值，那么任何剩余元素是第二个到最小值的概率与如果真正的最小值被移除（并且从未生成）的概率相同，那个元素将是新的分钟。这看起来很明显，但我认为由于某些条件概率问题，其他分布可能不是这样。

使用事实1，我们知道选择单个元素可以通过生成速率参数等于权重的指数分布样本，然后选择具有最小值的指数分布样本来完成。

使用事实2，我们知道我们不必重新生成指数样本。相反，只需为每个元素生成一个元素，并使用最低样本的k元素。

找到最低k可以在O（n）中完成。使用Quickselect算法查找第k个元素，然后简单地再次通过所有元素并输出低于第k个的所有元素。

一个有用的说明：如果您无法立即访问库以生成指数分布样本，则可以通过以下方式轻松完成： -ln(rand())/weight