Sample 3 integers without replacement in C++

user_1100107 0
Viewed 129

I want to sample three integers among {0, 1, ..., n-1} without replacement.

Here is how I proceed so far:

#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};
}

This works but is there a better way?

I want to perform this sampling multiple times, in a loop. Is it time-consuming to redefine the samplers for each iteration?

For technical reasons, I am restricted to C++ 11.

c++11 random c++
2 Answers

You can sample without replacement from 0, ..., n - 1 without allocating any additional memory; elem is unneeded. The key is to simulate a few steps of the Fisher-Yates Shuffle, as seen in David Eisenstat's answer to my related question.

// 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};
}
user_18961690

Rather than using erase, you can replace the element chosen from the vector by the last element.

elems[i1] = elems[n - 1];

Then do the same for the second:

elems[i2] = elems[n - 2];

The time to construct the three uniform_int_distribution is minimal. Constructing elems will consume more time.

user_52316070
Related