Nombres aléatoires pondérés

J'essaie d'implémenter un nombre aléatoire pondéré. Actuellement, je me cogne la tête contre le mur et je n'arrive pas à comprendre cela.

Dans mon projet (Hold'em hand-range, analyse subjective de l'équité tout-en-un), j'utilise les fonctions aléatoires de Boost. Alors, disons que je veux choisir un nombre aléatoire entre 1 et 3 (donc 1, 2 ou 3). Le générateur de twister mersenne de Boost fonctionne comme un charme pour cela. Cependant, je veux que le choix soit pondéré par exemple comme ceci:

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

Boost a-t-il une sorte de fonctionnalité pour cela?

Il existe un algorithme simple pour choisir un article au hasard, où les articles ont des poids individuels:

1) calculer la somme de tous les poids

2) choisissez un nombre aléatoire égal ou supérieur à 0 et inférieur à la somme des poids

3) parcourez les articles un à la fois, en soustrayant leur poids de votre nombre aléatoire, jusqu'à ce que vous obteniez l'article où le nombre aléatoire est inférieur au poids de cet article

Pseudo-code illustrant ceci:

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

Cela devrait être simple pour s'adapter à vos conteneurs boost et autres.

Si vos poids sont rarement modifiés mais que vous en choisissez souvent un au hasard, et tant que votre conteneur stocke des pointeurs vers les objets ou compte plus de quelques dizaines d'articles (en gros, vous devez profiler pour savoir si cela aide ou empêche) , puis il y a une optimisation:

En stockant la somme des poids cumulés dans chaque article, vous pouvez utiliser une recherche binaire pour sélectionner l'article correspondant au poids de prélèvement.

Si vous ne connaissez pas le nombre d'éléments dans la liste, il existe un algorithme très soigné appelé échantillonnage de réservoir qui peut être adapté pour être pondéré.

Réponse mise à jour à une ancienne question. Vous pouvez facilement le faire en C ++ 11 avec juste le 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';
}

Sortie sur mon système:

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

Notez que la plupart du code ci-dessus est uniquement consacré à l'affichage et à l'analyse de la sortie. La génération réelle n'est que de quelques lignes de code. La sortie démontre que les «probabilités» demandées ont été obtenues. Vous devez diviser la sortie demandée par 1,5 car c'est à cela que s'ajoutent les requêtes.

Si vos poids changent plus lentement qu'ils ne sont dessinés, C ++ 11 discrete_distributionsera le plus simple:

#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...

Notez cependant que le c ++ 11 discrete_distributioncalcule toutes les sommes cumulées lors de l'initialisation. Habituellement, vous voulez cela car cela accélère le temps d'échantillonnage pour un coût O (N) unique. Mais pour une distribution en évolution rapide, cela entraînera un coût de calcul (et de mémoire) élevé. Par exemple, si les poids représentaient le nombre d'éléments et que chaque fois que vous en dessinez un, vous le supprimez, vous souhaiterez probablement un algorithme personnalisé.

La réponse de Will https://stackoverflow.com/a/1761646/837451 évite cette surcharge mais sera plus lente à tirer que le C ++ 11 car il ne peut pas utiliser la recherche binaire.

Pour voir qu'il fait cela, vous pouvez voir les lignes pertinentes ( /usr/include/c++/5/bits/random.tccsur mon installation 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;
    }

Ce que je fais lorsque j'ai besoin de peser des nombres, c'est d'utiliser un nombre aléatoire pour le poids.

Par exemple: j'ai besoin de générer des nombres aléatoires de 1 à 3 avec les poids suivants:

• 10% d'un nombre aléatoire pourrait être 1
• 30% d'un nombre aléatoire pourrait être 2
• 60% d'un nombre aléatoire pourrait être 3

Ensuite, j'utilise:

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

Avec cela, au hasard, il a 10% des probabilités d'être 1, 30% pour être 2 et 60% pour être 3.

Vous pouvez jouer avec lui selon vos besoins.

J'espère que je pourrais vous aider, bonne chance!

Construisez un sac (ou std :: vector) de tous les éléments qui peuvent être sélectionnés.
Assurez-vous que le nombre de chaque élément est proportionnel à votre pondération.

Exemple:

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

Ayez donc un sac avec 100 articles avec 60 1, 35 2 et 5 3.
Maintenant, triez le sac au hasard (std :: random_shuffle)

Choisissez les éléments du sac de manière séquentielle jusqu'à ce qu'il soit vide.
Une fois vide, re-randomisez le sac et recommencez.

Choisissez un nombre aléatoire sur [0,1), qui devrait être l'opérateur par défaut () pour un boost RNG. Choisissez l'élément avec la fonction de densité de probabilité cumulée> = ce nombre:

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
}

Où random01 () renvoie un double> = 0 et <1. Notez que ce qui précède ne nécessite pas que les probabilités totalisent 1; il les normalise pour vous.

p est juste une fonction affectant une probabilité à un élément de la collection [début, fin). Vous pouvez l'omettre (ou utiliser une identité) si vous avez juste une séquence de probabilités.

J'ai implémenté plusieurs algorithmes aléatoires pondérés simples .