Нужна помощь с рандомизацией выбора членов массива

#cpp

Есть двумерный массив. В нем записаны некоторые значения и вероятность в процентах
на их "выпадение". Как реализовать функцию, которая будет выбирать число из массива
с вероятностью, указанной в нем?
    

Ответы

Ответ 1

Вот моё решение. Только я вместо двумерного массива сделал массив пар, так вроде
проще и наглядней, массив входной c_probs содержит пары где первое значение это выбрасываемое
число, второй это его вероятность, вероятности могут быть не нормализованные т.е. в
сумме давать не ровно 1. Решение заключается просто в вычислении массива распределения,
или проще говоря кумулятивной вероятности, т.е. c_distr[i + 1] = c_probs[i].second
+ c_distr[i]. Далее просто рандомно выбрасывается вероятность prob из отрезка [0, c_distr[last]]
и бинарным поиском (для простоты используется std::upper_bound) находится индекс i
для которого c_distr[i - 1] <= prob < c_distr[i], в итоге результирующее число выброшенное
будет c_probs[i - 1].first.

Вот текст программы на C++, можно запустить онлайн:

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

enum {
    c_num_tests = 50,
};

int main() {
    // Значение вероятностей чисел.
    vector< pair > const c_probs = {{5.5, 0.1}, {7.1, 0.3}, {1.3,
0.05},};

    // Массив кумулятивных вероятностей или попросту распределение.
    vector c_distr(c_probs.size() + 1);
    for (size_t i = 0; i < c_distr.size() - 1; ++i) c_distr[i + 1] = c_probs[i].second
+ c_distr[i];

    // Стандартный генератор чисел.    
    std::random_device r_dev;
    std::default_random_engine engine(r_dev());
    std::uniform_real_distribution distribution(0, c_distr.back());
    auto rng = std::bind(distribution, engine);

    // Генерируем точечные значения вероятности и определяем в какой индекс c_distr
они попали.
    for (size_t i_test = 0; i_test < c_num_tests; ++i_test) {
        double prob = rng();
        // Просто находит такой индекс i, что c_distr[i - 1] <= prob < c_distr[i].
        int i = std::upper_bound(c_distr.begin(), c_distr.end(), prob) - c_distr.begin();
        // Выводим просто число с индексом i - 1.
        cout << c_probs[i - 1].first << " ";
    }
    cout << endl;

    return 0;
}


Как предложил Vladimir Gamalyan, можно использовать уже готовый класс std::discrete_distribution,
он как раз делает то что я делал вручную выше, вот с ним более простое решение, можно
запустить онлайн:

#include 
#include 
#include 
#include 
#include 
using namespace std;

enum {
    c_num_tests = 50,
};

int main() {
    // Значение вероятностей чисел.
    vector< pair > const c_probs = {{5.5, 0.1}, {7.1, 0.3}, {1.3,
0.05},};

    // Сохраняем только веса.
    vector c_weights(c_probs.size());
    for (size_t i = 0; i < c_probs.size(); ++i) c_weights[i] = c_probs[i].second;

    // Стандартный генератор чисел.    
    std::random_device r_dev;
    std::default_random_engine engine(r_dev());
    std::discrete_distribution distribution(c_weights.begin(), c_weights.end());
    auto rng = std::bind(distribution, engine);

    // Генерируем числа с заданными весами.
    for (size_t i = 0; i < c_num_tests; ++i) {
        cout << c_probs[rng()].first << " ";
    }
    cout << endl;

    return 0;
}