Random Sample With replacement

Question

I draw a blank here: How do you sample with replacement in C++ (not using boost), but all members of std:: are ok. I mean what is the approach (or the function if we can twist a member of std:: to do this).

To provide some context, I want to sample (with replacement) k elements from an array Data[n] of n doubles.

@jamesdlin: this is for sampling *without* replacement right? — user189035, Feb 16 '16 at 22:04
@AmiTavory: Oops, you're right. I mixed up the meaning of "without replacement" and "with replacement" since the Fisher-Yates shuffle replaces the randomly selected item. — jamesdlin, Feb 16 '16 at 22:08
Isn't this trivial, am I missing something?With replacement: if your vector has *n* elements, just select *k* times a random number between *0* and *n-1*, take those elements. — Georg Schölly, Feb 16 '16 at 22:16

score 3 · Accepted Answer · edited May 23 '17 at 12:23

Given a function random_num_in_range (more on that later), it shouldn't be that hard to roll your own sampler:

// Samples randomly from (b, e) into o, n elements
template<typename It, typename OutIt>
void sample(It b, It e, OutIt o, size_t n)
{
    // Number of elements in range.
    const size_t s = std::distance(b, e);
    // Generate n samples.
    for(size_t i = 0; i < n; ++i)
    {
        It it = b;
        // Move b iterator random number of steps forward.
        std::advance(it, random_num_in_range(s));
        // Write into output
        *(o++) = *it;
    }
}

You'd use it possibly like this:

vector<int> input;
...
vector<int> output;
sample(input.begin(), input.end(), back_inserter(output), 100);

The question is how to write random_number_in_range without contemporary libraries. I suggest you look at this question, but skip past the accepted answer (which I've flagged for moderator attention, as I believe someone edited it into something completely wrong).

That's fine: random_number_in_range can be obtained from std:: (c++11) — user189035, Feb 16 '16 at 22:17
so `random_num_in_range(s)` produces a random integer in [0,s-1]? — user189035, Feb 16 '16 at 22:20

Random Sample With replacement

1 Answers1