从包含n个元素的向量中随机选择m个元素 [英] Choose m elements randomly from a vector containing n elements

问题描述

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

I have a vector containing n elements. I need to choose a subset of m elements randomly from the vector without repetition. What is the most efficient way of doing this? I need to do this several thousands of times in my code.

我想到的解决方案是使用 rand（）生成 0 和 n 之间的随机数 k $ c>。然后选择向量中的 k th元素，并将其插入到 std :: set 中。继续这样做，直到集合的大小等于 m 。我现在放心，该集合包含从 n 元素集合中随机选择的 m 个独特元素。

The solution on top of my mind is to use rand() to generate a random number k between 0 and n. Then pick the kth element in the vector and insert it into a std::set. Keep doing this till the set's size becomes equal to m. I am now assured that the set contains m unique elements randomly chosen from the set of n elements.

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

What are the other possible solutions?

谢谢。

推荐答案

您想要 Fisher-Yates shuffle （停止之后M次迭代）：

You want a Fisher-Yates shuffle (stop after M iterations):

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

在 http://ideone.com/3A3cv 。这显然比 std :: random_shuffle 快，当你只需要几个随机数的集合，并应该是大约相同的速度，即使 N == M 。

Demo at http://ideone.com/3A3cv. This is significantly faster than std::random_shuffle when you only need a few random numbers out of the set, and should be just about the same speed even if N==M.

这篇关于从包含n个元素的向量中随机选择m个元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！