c++ - How to select a value from a list with non-uniform probabilities?

Question

I am looking at the k-means++ initialization algorithm. The following two steps of the algorithm give rise to non-uniform probabilities:

For each data point x, compute D(x), the distance between x and the nearest center that has already been chosen.

Choose one new data point at random as a new center, using a weighted probability distribution where a point x is chosen with probability proportional to D(x)^2.

How can I select with this stated weighted probability distribution in C++?

Answer 1

Discrete distributions is a lot easier to do in C++11 with the random header and using std::discrete_distribution. This is example:

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

int main()
{
    std::random_device rd;
    std::mt19937 gen(rd());
    std::discrete_distribution<> d({20,30,40,10});
    std::map<int, int> m;
    for(int n=0; n<10000; ++n) {
        ++m[d(gen)];
    }
    for(auto p : m) {
        std::cout << p.first << " generated " << p.second << " times
";
    }
}

and this is a sample of the output:

0 generated 2003 times
1 generated 3014 times
2 generated 4021 times
3 generated 962 times