Génération de nombres aléatoires pondérés

Je voudrais générer des nombres aléatoires pondérés de manière exacte. Je peux expliquer exactement avec un exemple: Mon tableau d’entrée est [1, 2, 3] et leur poids est encore [1, 2, 3]. Dans ce cas, je m’attends à voir 1 pour 1 fois, 2 pour 2 fois et 3 pour 3. Comme 3 -> 2 -> 3 -> 1 -> 3 -> 2 …

J’implémente la génération de nombres aléatoires avec rand () pour obtenir une plage comprise entre [0, sum_of_weights). sum_of_weights = 1 + 2 + 3 = 6 pour l’exemple ci-dessus. J’ai cherché des solutions existantes sur Internet, mais le résultat n’est pas ce que je veux. Parfois, j’en ai 2 plus que 2 fois et pas 1 dans la séquence. C’est toujours pondéré mais pas exactement le nombre de fois que j’ai attendu.

Je ne suis pas sûr de ce qui ne va pas avec mon code ci-dessous. Devrais-je faire quelque chose de mal ou j’essaie totalement différent? Merci pour vos réponses.

int random_t (int items[], int items_weight[], int number_of_items) { double random_weight; double sum_of_weight = 0; int i; /* Calculate the sum of weights */ for (i = 0; i < number_of_items; i++) { sum_of_weight += items_weight[i]; } /* Choose a random number in the range [0,1) */ srand(time(NULL)); double g = rand() / ( (double) RAND_MAX + 1.0 ); random_weight = g * sum_of_weight; /* Find a random number wrt its weight */ int temp_total = 0; for (i = 0; i < number_of_items; i++) { temp_total += items_weight[i]; if (random_weight < temp_total) { return items[i]; } } return -1; /* Oops, we could not find a random number */ } 

J’ai aussi essayé quelque chose de différent (le code est ci-dessous). Cela a fonctionné pour mon cas, mais un débordement d’entier et une utilisation intensive de variables statiques le rendent problématique.

Si vous entrez un tableau d’entrée avant de donner NULL et de continuer à travailler avec. Un peu similaire à l’utilisation de strtok ().

 int random_w(int *arr, int weights[], int size) { int selected, i; int totalWeight; double ratio; static long int total; static long int *eachTotal = NULL; static int *local_arr = NULL; static double *weight = NULL; if (arr != NULL) { free(eachTotal); free(weight); eachTotal = (long int*) calloc(size, sizeof(long)); weight = (double*) calloc(size, sizeof(double)); total = 0; totalWeight = 0; local_arr = arr; for (i = 0; i < size; i++) { totalWeight += weights[i]; } for (i = 0; i < size; i++) { weight[i] = (double)weights[i] / totalWeight; } srand(time(NULL)); } while (1) { selected = rand() % size; ratio = (double)(eachTotal[selected])/(double)(total+1); if (ratio < weight[selected]) { total++; eachTotal[selected]++; return local_arr[selected]; } } } 

c’est ce que tu veux?

 # Weights: one 1, two 2s, three 3s >>> import random >>> vals = [1] * 1 + [2] * 2 + [3] * 3 >>> random.shuffle(vals) >>> vals [2, 3, 1, 2, 3, 3] 

Edit: Oups, pour une raison quelconque, mon esprit a remplacé la balise C par celle de Python. Quoi qu’il en soit, je pense que ce que vous voulez, ce n’est pas des générateurs de nombres aléatoires “pondérés”, mais un mélange Cela devrait aider.

Quand vous dites que vous n’avez pas “exactement” le nombre de valeurs que vous attendiez pour chaque valeur pondérée, combien de pistes parlez-vous? Si vous ne réalisiez que six exécutions aléatoires, je ne m’attendrais pas à ce que vous soyez en mesure de dire de manière définitive que tout fonctionne ou non. Votre code peut fonctionner correctement. Essayez de l’exécuter un million de fois et vérifiez les résultats. Ou peut-être voulez-vous réellement ce dont Nathon parle, une liste de valeurs vérifiées au préalable, que vous pouvez ensuite mélanger de manière aléatoire tout en conservant le poids exact que vous recherchez.

Vous pouvez échantillonner à partir d’une dissortingbution multinomiale . Votre univers d’échantillons aléatoires (ou “urne de balles dans un seau”) est {1, 2, 3} et les probabilités (“poids”) d’observer chacun sont respectivement {1/6, 2/6, 3/6} .

À des fins de démonstration, un script Perl peut vous fournir une liste d’observations de billes étiquetées avec les probabilités suivantes:

 #!/usr/bin/perl use ssortingct; use warnings; use Math::Random qw(random_multinomial); use Data::Dumper; my $events = 10; my @probabilities = qw(0.167 0.333 0.5); my @observations = random_multinomial($events, @probabilities); print Dumper \@observations; 

Pour 10 événements, un seul essai renverra quelque chose comme:

 $VAR1 = 1; $VAR2 = 2; $VAR3 = 7; 

Cela signifie que vous avez (à partir de cet essai unique) un événement étiqueté 1 , deux événements étiquetés 2 et sept événements étiquetés 3 .

Si vous répétez l’essai, vous obtiendrez peut-être une dissortingbution différente d’événements à 1 , 2 et 3 étiquettes.

Vous pouvez facilement construire une liste à partir de celle-ci en une liste équivalente {1, 2, 2, 3, 3, 3, 3, 3, 3, 3} .

Mélangez simplement cette seconde liste au hasard pour obtenir votre liste pondérée et observée de nombres aléatoires.

Si vous voulez que les fréquences d’échantillonnage soient complètement déterministes, je pense que la meilleure solution consiste à générer un tableau contenant le nombre approprié d’occurrences pour chaque valeur, puis à effectuer un armsage aléatoire (qui préserve les fréquences) et à prendre des éléments successifs du paramètre. tableau mélangé comme votre séquence aléatoire.

ok, ma réponse ressemblera à un bidouillage – mais bref ou en écrivant votre propre dissortingbution – peut-être que vous pouvez mapper une dissortingbution uniforme et augmenter l’effet de levier (consultez http://www.boost.org/doc/libs/1_44_0/doc/html /boost_random/reference.html#boost_random.reference.dissortingbutions )

en suivant votre exemple:

  • 1 -> 1
  • 2,3 -> 2
  • 4,5,6 -> 3
  • 7,8,9,10 -> 4 (etc …)

puis générez un nombre aléatoire compris entre 1 et 10 et renvoyez l’élément mappé. puis utilisez la dissortingbution uniform_int de boost pour obtenir un nombre que vous mappez ensuite.

voici un exemple de génération de nombres; vous devrez ensuite cartographier les résultats:

 #include  #include  #include  using namespace std; using namespace boost; int main ( ) { uniform_int<> distribution(0, 10) ; mt19937 engine; engine.seed(time(NULL)); variate_generator > myrandom (engine, dissortingbution); cout << myrandom() << endl; }