Selection sampling without replacement (following Knuth's algorithm S)

selection_without_replacement.cc

#include <iostream>
#include <limits>
#include <random>
#include <vector>

int main(int, char**)
{
  std::random_device r;
  std::default_random_engine e( r() );

  std::uniform_real_distribution<> U( 0, std::nextafter(1.0, std::numeric_limits<double>::max() ) );

  unsigned N = 20;
  unsigned n = 10;

  std::vector<unsigned> selected;
  selected.reserve(n);

  for( unsigned t = 0; t < N; t++ )
  {
    if( (N-t) * U( e ) < n - selected.size() )
      selected.push_back(t);

    if( selected.size() == n )
      break;
  }

  std::cout << "Selected items:";
  for( auto&& s : selected )
    std::cout << " " << s;
  std::cout << "\n";
}