从一个集合中选择N个随机数

Question

我有一个有序集（std :: set是精确的），它包含具有赋值权重的元素。我想从这个集合中随机选择N个元素，而更高权重的元素应该有更大的选择概率。任何元素都可以选择多次。

我想尽可能有效地做到这一点 - 我想避免任何复制集（它可能会非常大），并在O（N）时间运行，如果有可能的话。我正在使用C++，并希望坚持仅STL + Boost解决方案。

有没有人知道在STL/Boost中是否有函数执行这个任务？如果不是，如何实施？

Answer 1

您需要计算（并可能缓存，如果您认为性能）所有权重的总和。然后，生成N个随机数，直到该值。最后，重复你的设置，计算你到目前为止遇到的权重的总和。检查所有（剩余的）随机数。如果数字位于总和的前一个值和下一个值之间，请插入该值中的值并删除您的随机数。当你的随机数字列表为空或者你已经到达集合的结尾时停止。

Answer 2

我不知道任何库，但它听起来像你有一个加权轮盘赌轮。以下是一些伪代码的参考，尽管上下文与遗传算法有关：http://www.cse.unr.edu/~banerjee/selection.htm

至于“尽可能高效”，这取决于数据的某些特性。在加权轮盘赌轮的应用中，当搜索索引时，您可以考虑使用二分法搜索。但是，轮盘的每个插槽的可能性并不相同，因此按照它们的权重来检查它们可能是有意义的。

Answer 3

很大程度上取决于您愿意花费多少额外的存储空间来加快选择。

如果您不愿意使用任何额外的存储空间，@Alex Emelianov的回答几乎就是我想要发布的内容。如果你愿意使用一些额外的存储空间（可能还有一个不同于std::set的数据结构），你可以创建一个树（比如一个集合使用），但是在树的每个节点上，你还可以存储（加权）数量的项目在该节点的左侧。这将使您可以将生成的数字映射到与对数（而非线性）复杂度相关的正确关联值。