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

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

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

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

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

надеюсь, что я мог бы помочь Вам, удачи!

если ваши веса меняются медленнее, чем они рисуются, 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 install):

  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;
    }

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

пример:

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

Так что есть сумка с 100 пунктов с 60 1-х, 35 2-х и 5 3-х.
Теперь случайным образом сортировать сумку (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 () возвращает double >=0 и

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

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