C++ randomly sample k numbers from range 0:n-1 (n > k) without replacement

Question

I'm working on porting a MATLAB simulation into C++. To do this, I am trying to replicate MATLAB's randsample() function. I haven't figured out an efficient way to do this yet.

So I ask you all, how do I best randomly sample k numbers from a range 0:n-1 (for n > k) without replacement in C++?

I've considered the following pseudocode (inspired by the third example on cppreference.com), but I feel like it's a bit hacky:

initialize vect<int> v of size n
for i = 0 to n-1
    v[i] = i
shuffle v
return v[0 to k-1]

The drawback here is also the requirement to build a massive array first too. That seems like slow/clunky overkill.

I would love some direction here if you can help. I'm less interested in the theory (algorithms are interesting but not relevant to my needs now) than the best way to implement this in C++.

Thanks in advance!

Answer 1

As pointed out in Yksisarvinen 's answer, C++17 provides std::sample in <algorithm> that should be useful. Unfortunately its use of iterators makes working directly with integers awkward, i.e. not building a large temporary array/vector, and the only way I've got it working usefully was with lots of boilerplate code:

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

template<typename I>
class boxed_iterator {
    I i;

public:
    typedef I difference_type;
    typedef I value_type;
    typedef I pointer;
    typedef I reference;
    typedef std::random_access_iterator_tag iterator_category;

    boxed_iterator(I i) : i{i} {}

    bool operator==(boxed_iterator<I> &other) { return i == other.i; }
    I operator-(boxed_iterator<I> &other) { return i - other.i; }
    I operator++() { return i++; }
    I operator*() { return i; }
};

Giving us something not too painful to use with std::sample:

int main()
{
    std::vector<int> result;

    auto rng = std::mt19937{std::random_device{}()};

    // sample five values without replacement from [1, 100]
    std::sample(
        boxed_iterator{1}, boxed_iterator{101},
        std::back_inserter(result), 5, rng);

    for (auto i : result) {
        std::cout << i << ' ';
    }
}

It would be nice if boxed_iterator wasn't needed, it would be great if somebody could show me how!