Reputation: 25560

c++, how randomly with given probabilities choose numbers

I have N numbers n_1, n_2, ...n_N and associated probabilities p_1, p_2, ..., p_N. function should return number n_i with probability p_i, where i =1, ..., N. How model it in c++?
I know it is not a hard problem. But I am new to c++, want to know what function will you use. Will you generate uniform random number between 0 and 1 like this:

((double) rand() / (RAND_MAX+1))

Upvotes: 5

Answers (4)

Matthew D. Scholefield

Reputation: 3336

If you know the probabilities compile-time you can use this variadic template version I decided to create. Although in actuality, I don't recommend using this due to how horribly incomprehensible the source is :P.

Usage

NumChooser <
    Entry<2, 10>, // Value of 2 and relative probability of 10
    Entry<5, 50>,
    Entry<6, 80>,
    Entry<20, 01>
> chooser;

chooser.choose(); // Returns the number 2 on average 10/141 times, etc.

Efficiency

Ideone Generally, the template based implementation is very similar to a basic one. However, there are a few differences:

With -O2 optimizations or no optimizations, the template version can be ~1-5% slower
With -O3 optimizations, the template version was actually ~1% faster when generating numbers for 1 - 10,000 times consecutively.

Notes

This uses rand() for choosing numbers. If being statistically accurate is important to you or you would like to use C++11's <random>, you can use the slightly modified version below the first source.

Source

Ideone

#define onlyAtEnd(a) typename std::enable_if<sizeof...(a) == 0 > ::type

template<int a, int b>
class Entry
{
public:
    static constexpr int VAL = a;
    static constexpr int PROB = b;
};

template<typename... EntryTypes>
class NumChooser
{
private:
    const int SUM;
    static constexpr int NUM_VALS = sizeof...(EntryTypes);

public:
    static constexpr int size()
    {
        return NUM_VALS;
    }

    template<typename T, typename... args>
    constexpr int calcSum()
    {
        return T::PROB + calcSum < args...>();
    }

    template <typename... Ts, typename = onlyAtEnd(Ts) >
    constexpr int calcSum()
    {
        return 0;
    }

    NumChooser() : SUM(calcSum < EntryTypes... >()) { }

    template<typename T, typename... args>
    constexpr int find(int left, int previous = 0)
    {
        return left < 0 ? previous : find < args... >(left - T::PROB, T::VAL);
    }

    template <typename... Ts, typename = onlyAtEnd(Ts) >
    constexpr int find(int left, int previous)
    {
        return previous;
    }

    constexpr int choose()
    {
        return find < EntryTypes... >(rand() % SUM);
    }
};

C++11 `<random>` version

Ideone

#include <random>
#define onlyAtEnd(a) typename std::enable_if<sizeof...(a) == 0 > ::type

template<int a, int b>
class Entry
{
public:
    static constexpr int VAL = a;
    static constexpr int PROB = b;
};

template<typename... EntryTypes>
class NumChooser
{
private:
    const int SUM;
    static constexpr int NUM_VALS = sizeof...(EntryTypes);
    std::mt19937 gen;
    std::uniform_int_distribution<> dist;

public:

    static constexpr int size()
    {
        return NUM_VALS;
    }

    template<typename T, typename... args>
    constexpr int calcSum()
    {
        return T::PROB + calcSum < args...>();
    }

    template <typename... Ts, typename = onlyAtEnd(Ts) >
    constexpr int calcSum()
    {
        return 0;
    }

    NumChooser() : SUM(calcSum < EntryTypes... >()), gen(std::random_device{}()), dist(1, SUM) { }

    template<typename T, typename... args>
    constexpr int find(int left, int previous = 0)
    {
        return left < 0 ? previous : find < args... >(left - T::PROB, T::VAL);
    }

    template <typename... Ts, typename = onlyAtEnd(Ts) >
    constexpr int find(int left, int previous)
    {
        return previous;
    }

    int choose()
    {
        return find < EntryTypes... >(dist(gen));
    }
};

// Same usage as example above

Upvotes: 1

Tomasz Andel

Reputation: 173

Here you have a correct answer in my last comment:

how-to-select-a-value-from-a-list-with-non-uniform-probabilities

Upvotes: 0

Basile Starynkevitch

Reputation: 1

Perhaps something like (untested code!)

/* n is the size of tables, numtab[i] the number of index i, 
   probtab[i] its probability; the sum of all probtab should be 1.0 */
int random_inside(int n, int numtab[], double probtab[])
{
  double r = drand48();
  double p = 0.0;
  for (int i=0; i<n; i++) {
    p += probtab[i];
    if (r>=p) return numtab[i];
  }
}

Upvotes: 0

Mysticial

Reputation: 471209

This is very similar to the answer I gave for this question:

changing probability of getting a random number

You can do it like this:

double val = (double)rand() / RAND_MAX;

int random;
if (val < p_1)
    random = n_1;
else if (val < p_1 + p_2)
    random = n_2;
else if (val < p_1 + p_2 + p_3)
    random = n_3;
else
    random = n_4;

Of course, this approach only makes sense if p_1 + p_2 + p_3 + p_4 == 1.0.

This can easily be generalized to a variable number of outputs and probabilities with a couple of arrays and a simple loop.

Upvotes: 6