4

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

10
  • не хватает информации. Как выбирается вероятность из 2 измерения массива?
    – IC_
    12 ноя 2017 в 13:59
  • К примеру, arr [0][0] - значение, а arr[0][1] - вероятность его выпадения. 12 ноя 2017 в 14:01
  • Все равно не понятно. Есть у вас arr[7][42], у меня выпало 7. Откуда мне брать 42, чтобы получать элемент массива? 12 ноя 2017 в 14:03
  • Циркулярка. Нужно узнать вероятность выбранного элемента, который выбирается рандомно с вероятностью, которую нужно узнать?
    – IC_
    12 ноя 2017 в 14:04
  • @АндрейЛобанович Наверное имелось ввиду не двумерный массив а одномерный где p[n] это вероятность выпадения числа n. Может есть полное условие точное задачи?
    – Arty
    12 ноя 2017 в 14:04

1 ответ 1

4

Вот моё решение. Только я вместо двумерного массива сделал массив пар, так вроде проще и наглядней, массив входной 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 <iostream>
#include <random>
#include <functional>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

enum {
    c_num_tests = 50,
};

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

    // Массив кумулятивных вероятностей или попросту распределение.
    vector<double> 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<double> 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 <random>
#include <vector>
#include <utility>
#include <iostream>
#include <functional>
using namespace std;

enum {
    c_num_tests = 50,
};

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

    // Сохраняем только веса.
    vector<double> 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<size_t> 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;
}
2
  • 1
    Можно также использовать std::discrete_distribution, чтобы не писать выборку самому. 12 ноя 2017 в 15:06
  • @VladimirGamalyan Очень хорошее предложение, я даже не знал что есть discrete_distribution, она в самый раз подходит, я по сути просто её аналог вручную и реализовал.
    – Arty
    12 ноя 2017 в 15:21

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.