c++ - 从包含 n 个元素的 vector 中随机选择 m 个元素

Question

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

我想到的解决方案是使用 rand() 在 0 和 n 之间生成一个随机数 k 。然后选择 vector 中的第 k 个元素并将其插入到 std::set 中。继续这样做，直到集合的大小等于 m。我现在确信该集合包含从 n 元素集合中随机选择的 m 个唯一元素。

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

谢谢。

Answer 1

你想要一个 Fisher-Yates shuffle (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 也应该是差不多的速度.