Extract values from a set according to a given probability distribution

Question

I have to tackle this problem:

vector<int> myset={1,2,3,4};
vector<double> distribution ={0.01,0.1,0.3,0.59};

I have to pick a number of values from myset according to given distribution. Actually distribution and myset aren't fixed. They are of the same dimension, but this dimension can change and be pretty large too. I could uniformly extract a number in the range [0 100] and do like this:

int extracted_numb;
int numb = rand(0,100);
if(numb<1)
  extracted_numb=myset[0];
else if(numb<11)
  extracted_numb=myset[1];
else if(numb<41)
  extracted_numb=myset[2];
else
  extracted_numb=myset[3];

But I repeat, I don't know in the real case the dimension of distribution and myset (because is a user parameter) and thus I don't know how many if to do.

I ask if there is a good algorithm for this problem, and maybe some native library of C++ or in Boost that already accomplish it

(I'm using Boost 1.63 and C++11)

Answer 1

With C++11, use random::discrete_distribution to select an index into myset. (Boost has a similar function.)

Example (adapted from the cppreference link):

#include <iostream>
#include <map>
#include <random>
#include <vector>

int main()
{
    std::vector<int> myset = {10,22,35,47};
    std::vector<double> distribution = {0.01,0.1,0.3,0.59};
    std::random_device rd;
    std::mt19937 gen(rd());
    std::discrete_distribution<> d(distribution.begin(), distribution.end());
    std::map<int, int> m;
    for(int n=0; n<10000; ++n) {
        ++m[myset[d(gen)]];
    }
    for(auto p : m) {
        std::cout << p.first << " generated " << p.second << " times\n";
    }
}

(Live on coliru)