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

Question

C++。 Visual Studio 2010。

我有一个 std::vector V 的 N 个唯一元素(heavy 结构)。如何有效地从中挑选出 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；将它们用作 索引 到您的原始 vector 中。

通过使用 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使用您选择的随机数生成器；详情请查看文档。