obtenir un élément aléatoire pondéré

51

J'ai, par exemple, cette table

+ ----------------- +
| des fruits | poids |
+ ----------------- +
| pomme | 4 |
| orange | 2 |
| citron | 1 |
+ ----------------- +

J'ai besoin de retourner un fruit au hasard. Mais les pommes doivent être cueillies 4 fois plus souvent que le citron et 2 fois plus souvent que l’ orange .

Dans des cas plus généraux, cela devrait être f(weight)souvent.

Qu'est-ce qu'un bon algorithme général pour implémenter ce comportement?

Ou peut-être y a-t-il des joyaux prêts sur Ruby? :)

Post-
scripting J'ai implémenté l'algorithme actuel dans Ruby https://github.com/fl00r/pickup

fl00r
la source
11
cela devrait être la même formule pour obtenir un butin au hasard dans Diablo :-)
Jalayn
1
@Jalayn: En fait, l'idée de la solution d'intervalle décrite dans ma réponse ci-dessous vient de ce dont je me souviens au sujet des tables de combat dans World of Warcraft. :-D
Benjamin Kloster
Voir aussi
BlueRaja - Danny Pflughoeft le
J'ai implémenté plusieurs algorithmes aléatoires pondérés simples . Faites moi savoir si vous avez des questions.
Leonid Ganeline

Réponses:

50

La solution conceptuellement la plus simple serait de créer une liste dans laquelle chaque élément apparaît autant de fois que son poids.

fruits = [apple, apple, apple, apple, orange, orange, lemon]

Ensuite, utilisez les fonctions que vous avez à votre disposition pour choisir un élément aléatoire de cette liste (par exemple, générer un index aléatoire dans la plage appropriée). Ceci n’est bien sûr pas très efficace en mémoire et nécessite des poids entiers.


Une autre approche légèrement plus compliquée ressemblerait à ceci:

  1. Calculez les sommes cumulées de poids:

    intervals = [4, 6, 7]

    Où un indice inférieur à 4 représente une pomme , 4 à moins de 6 une orange et 6 à moins de 7 un citron .

  2. Générez un nombre aléatoire ncompris entre 0et sum(weights).

  3. Recherchez le dernier élément dont la somme cumulée est supérieure n. Le fruit correspondant est votre résultat.

Cette approche nécessite un code plus compliqué que le premier, mais moins de mémoire et de calcul, et supporte les poids en virgule flottante.

Pour l’un ou l’autre algorithme, l’étape de configuration peut être effectuée une fois pour un nombre arbitraire de sélections aléatoires.

Benjamin Kloster
la source
2
la solution d'intervalle semble bien
Jalayn
1
Il s'agissait de ma première pensée :). Mais que se passe-t-il si j'ai une table avec 100 fruits et que le poids pourrait être d'environ 10k? Ce sera très grand tableau et ce ne sera pas aussi efficace que je veux. C'est à propos de la première solution. La deuxième solution a l'air bien
fl00r
1
J'ai implémenté cet algorithme dans Ruby github.com/fl00r/pickup
fl00r
1
La méthode alias est le moyen le plus simple de gérer cela. Je suis franchement étonnée du nombre de publications qui répètent le même code encore et encore, tout en ignorant la méthode alias . pour l'amour de Dieu, vous obtenez des performances constantes!
opa
30

Voici un algorithme (en C #) qui permet de sélectionner un élément pondéré de manière aléatoire à partir de n’importe quelle séquence, en effectuant une itération unique:

public static T Random<T>(this IEnumerable<T> enumerable, Func<T, int> weightFunc)
{
    int totalWeight = 0; // this stores sum of weights of all elements before current
    T selected = default(T); // currently selected element
    foreach (var data in enumerable)
    {
        int weight = weightFunc(data); // weight of current element
        int r = Random.Next(totalWeight + weight); // random value
        if (r >= totalWeight) // probability of this is weight/(totalWeight+weight)
            selected = data; // it is the probability of discarding last selected element and selecting current one instead
        totalWeight += weight; // increase weight sum
    }

    return selected; // when iterations end, selected is some element of sequence. 
}

Ceci est basé sur le raisonnement suivant: sélectionnons le premier élément de notre séquence comme "résultat actuel"; ensuite, à chaque itération, conservez-le ou supprimez-le et choisissez le nouvel élément comme courant. Nous pouvons calculer la probabilité qu'un élément donné soit finalement sélectionné en tant que produit de toutes les probabilités qu'il ne soit pas ignoré lors des étapes suivantes, multiplié par la probabilité qu'il soit sélectionné en premier lieu. Si vous faites le calcul, vous verrez que ce produit se simplifie à (poids de l'élément) / (somme de tous les poids), ce qui est exactement ce dont nous avons besoin!

Etant donné que cette méthode itère une seule fois sur la séquence en entrée, elle fonctionne même avec des séquences d'une taille très grande, à condition que la somme des poids corresponde à un int(ou que vous puissiez choisir un type plus grand pour ce compteur).

Ça ne fait rien
la source
2
Je comparerais cela avant de supposer que c'est mieux simplement parce que ça répète une fois. Générer autant de valeurs aléatoires n'est pas vraiment rapide non plus.
Jean-Bernard Pellerin
1
@ Jean-Bernard Pellerin Je l'ai fait, et c'est en fait plus rapide sur les grandes listes. Sauf si vous utilisez un générateur aléatoire très puissant (-8
Nevermind, le
Devrait être la réponse acceptée imo. J'aime mieux cela que l'approche "intervalle" et "entrée répétée".
Vivin Paliath le
2
Je voulais juste dire que je suis revenu sur ce fil 3 ou 4 fois au cours des deux dernières années pour utiliser cette méthode. Cette méthode a à plusieurs reprises réussi à fournir les réponses dont j'ai besoin assez rapidement pour mes besoins. J'aimerais pouvoir faire passer cette réponse à chaque fois que je reviendrais pour l'utiliser.
Jim Yarbro
1
Belle solution si vous n'avez vraiment qu'à choisir une fois. Sinon, le travail préparatoire de la solution dans la première réponse est beaucoup plus efficace.
Déduplicateur
22

Les réponses déjà présentes sont bonnes et je les développerai un peu.

Comme Benjamin a suggéré les sommes cumulatives sont généralement utilisées dans ce genre de problème:

+------------------------+
| fruit  | weight | csum |
+------------------------+
| apple  |   4    |   4  |
| orange |   2    |   6  |
| lemon  |   1    |   7  |
+------------------------+

Pour trouver un élément dans cette structure, vous pouvez utiliser quelque chose comme un morceau de code de Nevermind. Ce morceau de code C # que j'utilise habituellement:

double r = Random.Next() * totalSum;
for(int i = 0; i < fruit.Count; i++)
{
    if (csum[i] > r)
        return fruit[i];
}

Passons maintenant à la partie intéressante. Quelle est l'efficacité de cette approche et quelle est la solution la plus efficace? Mon morceau de code nécessite une mémoire O (n) et s'exécute en un temps O (n) . Je ne pense pas que cela puisse être fait avec moins de O (n) espace, mais la complexité temporelle peut être beaucoup plus basse, O (log n) en fait. L'astuce consiste à utiliser la recherche binaire au lieu de la boucle régulière.

double r = Random.Next() * totalSum;
int lowGuess = 0;
int highGuess = fruit.Count - 1;

while (highGuess >= lowGuess)
{
    int guess = (lowGuess + highGuess) / 2;
    if ( csum[guess] < r)
        lowGuess = guess + 1;
    else if ( csum[guess] - weight[guess] > r)
        highGuess = guess - 1;
    else
        return fruit[guess];
}

Il y a aussi une histoire sur la mise à jour des poids. Dans le pire des cas, la mise à jour du poids d'un élément entraîne la mise à jour des sommes cumulatives de tous les éléments, ce qui augmente la complexité de la mise à jour à O (n) . Cela aussi peut être réduit à O (log n) en utilisant une arborescence indexée binaire .

Empereur Orionii
la source
Bon point sur la recherche binaire
fl00r
La réponse de Nevermind n'a pas besoin d'espace supplémentaire, donc c'est O (1), mais elle ajoute à la complexité de l'exécution en générant de manière répétée des nombres aléatoires et en évaluant la fonction de pondération (qui, en fonction du problème sous-jacent, pourrait être coûteuse).
Benjamin Kloster
1
Ce que vous prétendez être une "version plus lisible" de mon code ne l’est en réalité pas. Votre code doit connaître à l'avance la somme totale des poids et les sommes cumulées. le mien non.
Nevermind
@ Benjamin Kloster Mon code appelle uniquement la fonction de pondération une fois par élément - vous ne pouvez pas faire mieux que cela. Vous avez raison au sujet des nombres aléatoires, cependant.
Nevermind
@Nevermind: Vous ne l'appelez qu'une seule fois par appel de la fonction de sélection. Par conséquent, si l'utilisateur l'appelle deux fois, la fonction de pondération est appelée à nouveau pour chaque élément. Bien sûr, vous pouvez le mettre en cache, mais alors vous n'êtes plus O (1) pour la complexité de l'espace.
Benjamin Kloster
8

Ceci est une implémentation simple de Python:

from random import random

def select(container, weights):
    total_weight = float(sum(weights))
    rel_weight = [w / total_weight for w in weights]

    # Probability for each element
    probs = [sum(rel_weight[:i + 1]) for i in range(len(rel_weight))]

    slot = random()
    for (i, element) in enumerate(container):
        if slot <= probs[i]:
            break

    return element

et

population = ['apple','orange','lemon']
weights = [4, 2, 1]

print select(population, weights)

Dans les algorithmes génétiques, cette procédure de sélection est appelée sélection proportionnelle à la forme physique ou sélection à la roulette depuis:

  • une proportion de la roue est attribuée à chacune des sélections possibles en fonction de leur poids. Cela peut être obtenu en divisant le poids d'une sélection par le poids total de toutes les sélections, ce qui les normalise à 1.
  • ensuite, une sélection aléatoire est effectuée, similaire à la rotation de la roue de roulette.

Sélection de la roue de roulette

Les algorithmes classiques ont une complexité O (N) ou O (log N), mais vous pouvez également utiliser O (1) (par exemple, la sélection de la roulette via l'acceptation stochastique ).

manlio
la source
Savez-vous quelle est la source d'origine de cette image? Je veux l'utiliser pour un papier mais je dois m'assurer de l'attribution.
Malcolm MacLeod
@ MalcolmMacLeod Désolé, il est utilisé dans de nombreux articles / sites sur l'AG, mais je ne sais pas qui est l'auteur.
Manlio
0

Cet esprit fait exactement ce que vous demandez.

public static Random random = new Random(DateTime.Now.Millisecond);
public int chooseWithChance(params int[] args)
    {
        /*
         * This method takes number of chances and randomly chooses
         * one of them considering their chance to be choosen.    
         * e.g. 
         *   chooseWithChance(0,99) will most probably (%99) return 1
         *   chooseWithChance(99,1) will most probably (%99) return 0
         *   chooseWithChance(0,100) will always return 1.
         *   chooseWithChance(100,0) will always return 0.
         *   chooseWithChance(67,0) will always return 0.
         */
        int argCount = args.Length;
        int sumOfChances = 0;

        for (int i = 0; i < argCount; i++) {
            sumOfChances += args[i];
        }

        double randomDouble = random.NextDouble() * sumOfChances;

        while (sumOfChances > randomDouble)
        {
            sumOfChances -= args[argCount -1];
            argCount--;
        }

        return argCount-1;
    }

vous pouvez l'utiliser comme ça:

string[] fruits = new string[] { "apple", "orange", "lemon" };
int choosenOne = chooseWithChance(98,1,1);
Console.WriteLine(fruits[choosenOne]);

Le code ci-dessus renverra très probablement (% 98) 0, qui correspond à l'index de 'pomme' pour le tableau donné.

En outre, ce code teste la méthode fournie ci-dessus:

Console.WriteLine("Start...");
int flipCount = 100;
int headCount = 0;
int tailsCount = 0;

for (int i=0; i< flipCount; i++) {
    if (chooseWithChance(50,50) == 0)
        headCount++;
    else
        tailsCount++;
}

Console.WriteLine("Head count:"+ headCount);
Console.WriteLine("Tails count:"+ tailsCount);

Cela donne un résultat quelque chose comme ça:

Start...
Head count:52
Tails count:48
Ramazan POLAT
la source
2
Les programmeurs sont sur les questions conceptuelles et les réponses sont censées expliquer les choses. Lancer des vidages de code au lieu d'explications revient à copier le code d'un IDE sur un tableau: cela peut sembler familier et parfois même compréhensible, mais ça fait bizarre ... juste bizarre. Le tableau blanc n'a pas de compilateur
ça va
Vous avez raison, je me suis concentré sur le code, j'ai donc oublié de dire comment cela fonctionne. Je vais ajouter une explication sur la façon dont cela fonctionne.
Ramazan Polat