algorithm - 以概率从 n 中选择 k

Question

我有一个包含 n 个元素的列表 (e_i)。对于每个 i，e_i 都有概率 p_i 被选中。

我想编写一个算法从这 n 个元素中挑选 k 个元素，但我在选择它们时必须尊重每个元素的概率。我不知道该怎么做，我不知道有什么算法可以做到这一点:/

你能指引我的倒影吗？

Answer 1

假设您有 3 个可能的值:A、B、C 和:P(A) = 0.2，P(B) = 0.3，P(C) = 0.5。然后将累积概率放入数组 p = [0.2, 0.5, 1]。在每次选择中，您将生成一个 [0, 1] 范围内的随机数(使用您使用的语言的内置库)。根据该数字，您将返回大于或等于随机生成数字(实际上是对应于数字 A、B 或 C 的类别)的最小数字作为响应。

提示:如果使用最优方法，可以在 O(logN) 时间内获得该类。

举个例子:如果你生成值0.4，那么你将返回B，因为0.5是最小的数>= 0.4 .如果您生成 0.01，您将返回 A。

这就是想法，我会让您尝试实现它。如果您需要更多帮助，我也可以编写一些(伪)代码。