从一组唯一值中选择一个唯一的随机子集

Question

C++.Visual Studio 2010.

我有一个std::vectorN的独特元素(重结构).如何有效地从中挑选M个随机,独特的元素？

例如V包含10个元素:{0,1,2,3,4,5,6,7,8,9}我挑了三个......

• 4,0,9
• 0,7,8
• 但不是这个:0,5,5 <---不是唯一的!

STL是首选.那么,这样的事情呢？

std::minstd_rand gen; // linear congruential engine??
std::uniform_int<int> unif(0, v.size() - 1);
gen.seed((unsigned int)time(NULL));

// ...?

// Or is there a good solution using std::random_shuffle for heavy objects?

Answer 1

创建范围的随机排列0, 1, ..., N - 1并选择第一个M; 将它们用作原始载体的索引.

的随机排列是很容易通过使用与标准库取得std::iota连同std::random_shuffle:

std::vector<Heavy> v; // given

std::vector<unsigned int> indices(V.size());
std::iota(indices.begin(), indices.end(), 0);
std::random_shuffle(indices.begin(), indices.end());

// use V[indices[0]], V[indices[1]], ..., V[indices[M-1]]

您可以提供random_shuffle您选择的随机数发生器; 查看文档以获取详细信息.

Answer 2

大多数时候,Kerrek提供的方法就足够了.但是如果N非常大,并且M的数量级更小,则以下方法可能是优选的.

创建一组无符号整数,并在[0,N-1]范围内向其添加随机数,直到该集的大小为M.然后使用这些索引处的元素.

std::set<unsigned int> indices;
while (indices.size() < M)
    indices.insert(RandInt(0,N-1));