从包含 n 个元素的向量中随机选择 m 个元素

Question

我有一个包含 n 元素的向量。我需要从向量中随机选择 m 元素的子集而不重复。这样做最有效的方法是什么？我需要在我的代码中执行数千次。

The solution on top of my mind is to use rand() to generate a random number k between 0 and n .然后选择 k 向量中的第一个元素并将其插入 std::set 。继续这样做，直到集合的大小等于 m 。我现在确信该集合包含 m 从 n 元素集中随机选择的唯一元素。

其他可能的解决方案是什么？

谢谢。

原文由 Vinay 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

你想要一个 Fisher-Yates 洗牌（在 M 次迭代后停止）：

 template<class BidiIter >
BidiIter random_unique(BidiIter begin, BidiIter end, size_t num_random) {
    size_t left = std::distance(begin, end);
    while (num_random--) {
        BidiIter r = begin;
        std::advance(r, rand()%left);
        std::swap(*begin, *r);
        ++begin;
        --left;
    }
    return begin;
}

在 http://ideone.com/3A3cv 进行演示。这比 std::random_shuffle 当你只需要几个随机数时要快得多，即使 N==M 也应该是差不多的速度。

原文由 Michael Burr 发布，翻译遵循 CC BY-SA 3.0 许可协议