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

Question

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

我脑海中的解决方案是rand()用来生成和k之间的随机数.然后选择向量中的第th个元素并将其插入到.继续这样做直到集合的大小变得相等.我现在确信该集合包含从元素集中随机选择的唯一元素.0nkstd::setmmn

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

谢谢.

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.