Взвешенные случайные числа

Я пытаюсь реализовать взвешенные случайные числа. Я сейчас просто бьюсь головой об стену и не могу понять этого.

В своем проекте (диапазоны рук в холдеме, субъективный анализ эквити олл-ин) я использую случайные функции Boost. Итак, допустим, я хочу выбрать случайное число от 1 до 3 (то есть 1, 2 или 3). Генератор mersenne twister от Boost отлично справляется с этой задачей. Однако я хочу, чтобы выбор был взвешен, например, следующим образом:

1 (weight: 90)
2 (weight: 56)
3 (weight:  4)

Есть ли у Boost какие-то функции для этого?

Существует простой алгоритм случайного выбора предмета, при котором предметы имеют индивидуальный вес:

1) посчитайте сумму всех весов

2) выберите случайное число, которое равно 0 или больше и меньше суммы весов

3) просматривайте элементы по одному, вычитая их вес из случайного числа, пока не получите элемент, случайное число которого меньше веса этого элемента.

Псевдокод, иллюстрирующий это:

int sum_of_weight = 0;
for(int i=0; i<num_choices; i++) {
   sum_of_weight += choice_weight[i];
}
int rnd = random(sum_of_weight);
for(int i=0; i<num_choices; i++) {
  if(rnd < choice_weight[i])
    return i;
  rnd -= choice_weight[i];
}
assert(!"should never get here");

Это должно быть легко адаптировать к вашим буст-контейнерам и тому подобному.

Если ваши веса редко меняются, но вы часто выбираете один случайным образом, и пока ваш контейнер хранит указатели на объекты или имеет длину более нескольких десятков элементов (в основном, вы должны профилировать, чтобы знать, помогает это или мешает) , то идет оптимизация:

Сохраняя сумму совокупного веса в каждом элементе, вы можете использовать двоичный поиск, чтобы выбрать элемент, соответствующий весу выбора.

Если вы не знаете количество элементов в списке, тогда существует очень удобный алгоритм, называемый отбором проб резервуара, который можно адаптировать для взвешивания.

Обновленный ответ на старый вопрос. Вы можете легко сделать это в C ++ 11 с помощью только std :: lib:

#include <iostream>
#include <random>
#include <iterator>
#include <ctime>
#include <type_traits>
#include <cassert>

int main()
{
    // Set up distribution
    double interval[] = {1,   2,   3,   4};
    double weights[] =  {  .90, .56, .04};
    std::piecewise_constant_distribution<> dist(std::begin(interval),
                                                std::end(interval),
                                                std::begin(weights));
    // Choose generator
    std::mt19937 gen(std::time(0));  // seed as wanted
    // Demonstrate with N randomly generated numbers
    const unsigned N = 1000000;
    // Collect number of times each random number is generated
    double avg[std::extent<decltype(weights)>::value] = {0};
    for (unsigned i = 0; i < N; ++i)
    {
        // Generate random number using gen, distributed according to dist
        unsigned r = static_cast<unsigned>(dist(gen));
        // Sanity check
        assert(interval[0] <= r && r <= *(std::end(interval)-2));
        // Save r for statistical test of distribution
        avg[r - 1]++;
    }
    // Compute averages for distribution
    for (double* i = std::begin(avg); i < std::end(avg); ++i)
        *i /= N;
    // Display distribution
    for (unsigned i = 1; i <= std::extent<decltype(avg)>::value; ++i)
        std::cout << "avg[" << i << "] = " << avg[i-1] << '\n';
}

Вывод в моей системе:

avg[1] = 0.600115
avg[2] = 0.373341
avg[3] = 0.026544

Обратите внимание, что большая часть приведенного выше кода посвящена просто отображению и анализу вывода. Фактическая генерация - это всего лишь несколько строк кода. Выходные данные показывают, что запрошенные «вероятности» были получены. Вы должны разделить запрошенный вывод на 1,5, так как это то, к чему складываются запросы.

Если ваши веса изменяются медленнее, чем они нарисованы, C ++ 11 discrete_distributionбудет самым простым:

#include <random>
#include <vector>
std::vector<double> weights{90,56,4};
std::discrete_distribution<int> dist(std::begin(weights), std::end(weights));
std::mt19937 gen;
gen.seed(time(0));//if you want different results from different runs
int N = 100000;
std::vector<int> samples(N);
for(auto & i: samples)
    i = dist(gen);
//do something with your samples...

Однако обратите внимание, что c ++ 11 discrete_distributionвычисляет все совокупные суммы при инициализации. Обычно вам это нужно, потому что это ускоряет время выборки за разовую стоимость O (N). Но для быстро меняющегося дистрибутива это потребует больших затрат на вычисления (и память). Например, если веса представляют количество элементов, и каждый раз, когда вы рисуете один и удаляете его, вам, вероятно, понадобится собственный алгоритм.

Ответ Уилла https://stackoverflow.com/a/1761646/837451 позволяет избежать этих накладных расходов, но будет работать медленнее, чем C ++ 11, потому что он не может использовать двоичный поиск.

Чтобы убедиться в этом, вы можете увидеть соответствующие строки ( /usr/include/c++/5/bits/random.tccв моей установке Ubuntu 16.04 + GCC 5.3):

  template<typename _IntType>
    void
    discrete_distribution<_IntType>::param_type::
    _M_initialize()
    {
      if (_M_prob.size() < 2)
        {
          _M_prob.clear();
          return;
        }

      const double __sum = std::accumulate(_M_prob.begin(),
                                           _M_prob.end(), 0.0);
      // Now normalize the probabilites.
      __detail::__normalize(_M_prob.begin(), _M_prob.end(), _M_prob.begin(),
                            __sum);
      // Accumulate partial sums.
      _M_cp.reserve(_M_prob.size());
      std::partial_sum(_M_prob.begin(), _M_prob.end(),
                       std::back_inserter(_M_cp));
      // Make sure the last cumulative probability is one.
      _M_cp[_M_cp.size() - 1] = 1.0;
    }

Когда мне нужно взвесить числа, я использую случайное число для веса.

Например: мне нужно, чтобы сгенерировали случайные числа от 1 до 3 со следующими весами:

• 10% случайного числа может быть 1
• 30% случайного числа может быть 2
• 60% случайного числа может быть 3

Тогда использую:

weight = rand() % 10;

switch( weight ) {

    case 0:
        randomNumber = 1;
        break;
    case 1:
    case 2:
    case 3:
        randomNumber = 2;
        break;
    case 4:
    case 5:
    case 6:
    case 7:
    case 8:
    case 9:
        randomNumber = 3;
        break;
}

При этом случайным образом у 10% вероятностей будет 1, 30% - 2 и 60% - 3.

Вы можете играть с ним по своему усмотрению.

Надеюсь, я смогу вам помочь, удачи!

Создайте сумку (или std :: vector) из всех предметов, которые можно выбрать.
Убедитесь, что количество каждого элемента пропорционально вашему весу.

Пример:

• 1 60%
• 2 35%
• 3 5%

Так что имейте мешок со 100 предметами с 60 единицами, 35 двойками и 5 тройками.
Теперь случайным образом отсортируйте сумку (std :: random_shuffle)

Выбирайте элементы из пакета последовательно, пока он не опустеет.
После того, как мешок опустеет, перемешайте его заново и начните заново.

Выберите случайное число на [0,1), которое должно быть оператором по умолчанию () для повышения ГСЧ. Выберите элемент с кумулятивной функцией плотности вероятности> = это число:

template <class It,class P>
It choose_p(It begin,It end,P const& p)
{
    if (begin==end) return end;
    double sum=0.;
    for (It i=begin;i!=end;++i)
        sum+=p(*i);
    double choice=sum*random01();
    for (It i=begin;;) {
        choice -= p(*i);
        It r=i;
        ++i;
        if (choice<0 || i==end) return r;
    }
    return begin; //unreachable
}

Где random01 () возвращает двойное значение> = 0 и <1. Обратите внимание, что приведенное выше не требует суммирования вероятностей до 1; это нормализует их для вас.

p - это просто функция, присваивающая вероятность элементу в коллекции [начало, конец). Вы можете опустить его (или использовать идентификатор), если у вас есть просто последовательность вероятностей.

Я реализовал несколько простых взвешенных случайных алгоритмов .