How to sample without replacement using c++ uniform_int_distribution [duplicate]

Question

I want to use the uniform_int_distribution in the c++ random library. However, it only does the sampling with replacement, as in the example below. How can I sample without replacement?

#include <iostream>
#include <random>

int main()
{
  std::default_random_engine generator;
  std::uniform_int_distribution<int> distribution(1,4);

  for(int i=0; i<4; ++i)
    std::cout << distribution(generator) << std::endl;

  return 0;
}

Answer 1

Use std::shuffle on, say, a std::array<int> or a std::vector<int>, initialised to {1, 2, 3, 4}.

Then read back the container contents in order.

This will have better statistical properties than drawing a random number and accepting it only if it hasn't been drawn before.

Reference http://en.cppreference.com/w/cpp/algorithm/random_shuffle

Answer 2

As of c++17, there is now a standard library function which does exactly this. See https://en.cppreference.com/w/cpp/algorithm/sample

#include <iostream>
#include <random>
#include <string>
#include <iterator>
#include <algorithm>

int main()
{
    std::string in = "abcdefgh", out;
    std::sample(in.begin(), in.end(), std::back_inserter(out),
                5, std::mt19937{std::random_device{}()});
    std::cout << "five random letters out of " << in << " : " << out << '\n';
}

Answer 3

If you want to sample N uniformly distributed integers without replacement from the range [low, high), you can write this:

std::vector<int> array(N);   // or reserve space for N elements up front
 
auto gen = std::mt19937{std::random_device{}()};
    
std::ranges::sample(std::views::iota(low, high), 
                    array.begin(),
                    N, 
                    gen);

std::ranges::shuffle(array, gen);  // only if you want the samples in random order 

Here's a demo.

This is similar to Philip M's answer, but from C++20 the input range can be generated lazily.