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

Ответ 1

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

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");

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

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

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

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

Ответ 2

Обновлен ответ на старый вопрос. Вы можете легко сделать это на С++ 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, так как это то, к чему добавляют запросы.

Ответ 3

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

Например: мне нужно, чтобы генерировать случайные числа от 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.

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

Надеюсь, что смогу помочь тебе, Удачи!

Ответ 4

Если ваши веса изменяются медленнее, чем они нарисованы, С++ 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...

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

Будет отвечать fooobar.com/questions/79023/..., избегая этих издержек, но будет медленнее рисовать, чем С++ 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;
    }

Ответ 5

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

Пример:

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

Итак, у вас есть сумка с 100 предметами с 60 1, 35 2 и 5 3.
Теперь произвольно сортируйте сумку (std:: random_shuffle)

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

Ответ 6

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

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() возвращает double >= 0 и < 1. Заметим, что вышесказанное не требует, чтобы вероятности суммировались с 1; он нормализует их для вас.

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

Ответ 7

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