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

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

Ответ

Вот моё решение. Только я вместо двумерного массива сделал массив пар, так вроде проще и наглядней, массив входной 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; }