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

Question

C++。 Visual Studio 2010。

我有

std::vector

V 个独特元素（heavy 结构）。如何有效地从中挑选 M 个随机、独特的元素？

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

• 4,0,9
• 0,7,8
• 但不是这个：0, 5, 5 <--- not unique!

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));

Answer 3

既然你希望它高效，我认为你可以获得摊销

O(M)

，假设你必须多次执行该操作。然而，这种方法是不可重入的。

首先创建一个

static

（即

std::vector<...>::size_type

即可）值的局部（即

unsigned

）向量。

如果您输入函数，请调整向量大小以匹配

N

并用旧大小到

N-1

之间的值填充它：

static std::vector<unsigned> indices;
if (indices.size() < N) {
  indices.reserve(N);
  for (unsigned i = indices.size(); i < N; i++) {
    indices.push_back(i);
  }
}

然后，从该向量中随机选择

M

唯一的数字：

std::vector<unsigned> result;
result.reserver(M);
for (unsigned i = 0; i < M; i++) {
  unsigned const r = getRandomNumber(0,N-i); // random number < N-i
  result.push_back(indices[r]);
  indices[r] = indices[N-i-1];
  indices[N-i-1] = r;
}

现在，您的结果位于

result

向量中。

但是，您仍然需要在下一次运行中修复对

indices

的更改，以便

indices

再次变得单调：

for (unsigned i = N-M; i < N; i++) {
  // restore previously changed values
  indices[indices[i]] = indices[i];
  indices[i] = i;
}

但是，只有当您必须经常运行该算法并且

N

不会变得太大以至于您无法忍受

indices

一直消耗 RAM 时，这种方法才有用。

Answer 4

如果

M

足够小，以至于

M^2

小于

N log N

并且 您需要确定性运行时间（而不是“几乎总是”运行时间），那么您可以通过以下方式有效地选择“第 N 个最小的未选择值”保留先前选择的排序向量并“计算”未选择的值。

我认为这样的东西应该有效（我还没有测试过）。

std::vector<int> choice;
choice.reserve(M);
while (choice.size() < M) {
  // choice is reverse sorted.
  choice.emplace_back(RandBelow(N - choice.size()));
  auto i = choice.size() - 1;
  while (i > 1 && choice[i-1] <= choice[i]) {
    std::swap(choice[i], choice[i-1]);  // shift into place
    i--;
    choice[i]++; // Increment every time a value is passed.
  }
}

（注意：我 90% 确信可以对此进行优化，以减少约 50% 的写入量，并将

O(M^2)

与

O(M log M)

进行比较，但这个版本更适合说明。）

我怀疑类似的事情可以在

O(M log M)

时间内完成，使用某种平衡树来跟踪每个子树的大小，但我怀疑树的开销会使得这个向量版本中的一个或另一个或者更好的基本“洗牌所有索引”解决方案。