在C ++中采样3个整数而不进行替换

debugcn 发表于 Dev

斯蒂芬·洛朗（Stephane Laurent）

我想在其中三个整数之间进行采样{0, 1, ..., n-1}而不进行替换。

到目前为止，这是我的工作方式：

#include <random>

/* constructs vector {0, 1, ..., n-1} --------------------------------------- */
template <class T>
std::vector<T> integers_n(T n) {
  std::vector<T> out(n);
  for(T i = 0; i < n; i++) {
    out[i] = i;
  }
  return out;
}

/* samples three integers among {0, 1, ..., n-1} ---------------------------- */
const std::vector<int> choose3(const int n,
                               std::default_random_engine& generator) {
  std::uniform_int_distribution<int> sampler1(0, n - 1);
  std::uniform_int_distribution<int> sampler2(0, n - 2);
  std::uniform_int_distribution<int> sampler3(0, n - 3);
  const int i1 = sampler1(generator);
  const int i2 = sampler2(generator);
  const int i3 = sampler3(generator);
  std::vector<int> elems = integers_n(n);
  elems.erase(elems.begin() + i1);
  const int j2 = elems[i2];
  elems.erase(elems.begin() + i2);
  const int j3 = elems[i3];
  return {i1, j2, j3};
}

这有效，但是有更好的方法吗？

我想循环执行多次此采样。重新定义每次迭代的采样器是否很耗时？

由于技术原因，我只能使用C ++ 11。

贾斯汀

您可以在不进行替换的0, ..., n - 1情况下进行采样，而无需分配任何额外的内存。elem不需要。关键是模拟Fisher-Yates Shuffle的几个步骤，如David Eisenstat对我相关问题的回答所示。

// std::array<int, 3> requires no heap allocation, so is a better choice.
std::array<int, 3> choose3(const int n,
                           std::default_random_engine& generator) {
    std::uniform_int_distribution<int> sampler1(0, n - 1);
    std::uniform_int_distribution<int> sampler2(0, n - 2);
    std::uniform_int_distribution<int> sampler3(0, n - 3);
    // Algorithm translated from https://stackoverflow.com/a/64359519/1896169
    int i1 = sampler1(generator);
    int i2 = sampler2(generator);
    int i3 = sampler3(generator);

    if (i3 == i2) i3 = n - 2;
    if (i3 == i1) i3 = n - 1;
    if (i2 == i1) i2 = n - 1;
    return {i1, i2, i3};
}

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。