Nombres aléatoires pondérés

Question

J'essaie d'implémenter un système de nombres aléatoires pondérés. Je suis en train de me taper la tête contre le mur et je n'arrive pas à comprendre.

Dans mon projet (classement des mains en Hold'em, analyse subjective de l'équité all-in), j'utilise les fonctions aléatoires de Boost. Disons que je veux choisir un nombre aléatoire entre 1 et 3 (donc soit 1, 2 ou 3). Le générateur de mersenne twister 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)

Est-ce que Boost a une sorte de fonctionnalité pour cela ?

Answer 1

Il existe un algorithme simple pour choisir un élément au hasard, où les éléments ont des poids individuels :

1) calculer la somme de tous les poids

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

3) Passez en revue les éléments un par un, en soustrayant leur poids de votre nombre aléatoire, jusqu'à ce que vous obteniez l'élément pour lequel le nombre aléatoire est inférieur à son poids.

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 facile à adapter à vos conteneurs de boost et autres.

---

Si vos poids sont rarement modifiés mais que vous en choisissez souvent un au hasard, et pour autant que votre conteneur stocke des pointeurs vers les objets ou qu'il compte plus de quelques dizaines d'éléments (en gros, vous devez établir un profil pour savoir si cela vous aide ou vous gêne), alors il y a une optimisation :

En stockant la somme des poids cumulés dans chaque élément, vous pouvez utiliser une fonction recherche binaire pour choisir l'élément correspondant au poids du prélèvement.

---

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

Answer 2

Réponse actualisée à une vieille question. Vous pouvez facilement faire cela 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 majeure partie du code ci-dessus est consacrée à l'affichage et à l'analyse de la sortie. La génération proprement dite ne représente que quelques lignes de code. La sortie montre que les "probabilités" demandées ont été obtenues. Vous devez diviser la sortie demandée par 1,5 puisque c'est le total des demandes.

Answer 3

Ce que je fais quand j'ai besoin de pondérer des nombres, c'est 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 pondérations suivantes :

• 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

Alors 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% d'être 2 et 60% d'être 3.

Vous pouvez jouer avec selon vos besoins.

J'espère avoir pu vous aider, bonne chance !

Answer 4

Une façon vraiment naïve serait de remplir un tableau de 100 nombres et de mettre 90 1, 6 2 et 4 3 puis random(100) et d'utiliser ce nombre comme index pour le tableau. Pour rendre la chose plus intéressante, vous pouvez "mélanger" le tableau et voir si cela aide.

Answer 5

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

Exemple :

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

Nous avons donc un sac contenant 100 articles avec 60 1, 35 2 et 5 3.
Maintenant, triez aléatoirement le sac (std::random_shuffle)

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