gewichtetes zufälliges Item erhalten

51

Ich habe zum Beispiel diesen Tisch

+ ----------------- +
| Obst | gewicht |
+ ----------------- +
| Apfel | 4 |
| orange | 2 |
| Zitrone | 1 |
+ ----------------- +

Ich muss eine zufällige Frucht zurückgeben. Aber Apfel sollte 4-mal so häufig wie Zitrone und 2-mal so häufig wie Orange gepflückt werden .

Im allgemeineren Fall sollte es f(weight)mal häufig sein.

Was ist ein guter allgemeiner Algorithmus, um dieses Verhalten zu implementieren?

Oder gibt es vielleicht einige fertige Edelsteine ​​auf Ruby? :)

PS
Ich habe den aktuellen Algorithmus in Ruby https://github.com/fl00r/pickup implementiert

fl00r
quelle
11
Das sollte die gleiche Formel sein, um zufällige Beute in Diablo zu erhalten :-)
Jalayn
1
@Jalayn: Die Idee für die Intervalllösung in meiner Antwort unten stammt aus dem, woran ich mich bei Kampftabellen in World of Warcraft erinnere. :-D
Benjamin Kloster
Siehe auch
BlueRaja - Danny Pflughoeft
Ich habe mehrere einfache gewichtete Zufallsalgorithmen implementiert . Lass es mich wissen, wenn du fragen hast.
Leonid Ganeline

Antworten:

50

Die konzeptionell einfachste Lösung wäre, eine Liste zu erstellen, in der jedes Element so oft vorkommt, wie es gewichtet ist

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

Verwenden Sie dann die Funktionen, die Ihnen zur Verfügung stehen, um ein zufälliges Element aus dieser Liste auszuwählen (z. B. einen zufälligen Index im richtigen Bereich erstellen). Dies ist natürlich nicht sehr speichereffizient und erfordert ganzzahlige Gewichte.


Ein anderer, etwas komplizierterer Ansatz würde so aussehen:

  1. Berechnen Sie die kumulativen Summen der Gewichte:

    intervals = [4, 6, 7]

    Wenn ein Index unter 4 einen Apfel darstellt , 4 bis unter 6 eine Orange und 6 bis unter 7 eine Zitrone .

  2. Generieren Sie eine Zufallszahl nim Bereich von 0bis sum(weights).

  3. Suchen Sie das letzte Objekt, dessen kumulierte Summe über dem angegebenen Wert liegt n. Die entsprechende Frucht ist Ihr Ergebnis.

Dieser Ansatz erfordert komplizierteren Code als der erste, aber weniger Speicher und Berechnung und unterstützt Gleitkommagewichte.

Für jeden Algorithmus kann der Einrichtungsschritt einmal für eine beliebige Anzahl von Zufallsauswahlen durchgeführt werden.

Benjamin Kloster
quelle
2
Die Intervall-Lösung scheint schön
Jalayn
1
Das war mein erster Gedanke :). Aber was ist, wenn ich einen Tisch mit 100 Früchten habe und das Gewicht um die 10k liegen könnte? Es wird ein sehr großes Array sein und dies wird nicht so effizient sein, wie ich es möchte. Hier geht es um die erste Lösung. Zweite Lösung sieht gut aus
fl00r
1
Ich habe diesen Algorithmus in Ruby implementieren github.com/fl00r/pickup
fl00r
1
Die Alias-Methode ist auf jeden Fall der richtige Weg, um damit umzugehen. Ich bin ehrlich erstaunt über die Anzahl der Posts, die denselben Code immer wieder wiederholen und dabei die Alias-Methode ignorieren . um Himmels willen erhalten Sie konstante Zeitleistung!
Opa
30

Hier ist ein Algorithmus (in C #), mit dem zufällig gewichtetes Element aus einer beliebigen Sequenz ausgewählt und nur einmal durchlaufen werden kann:

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

Dies basiert auf der folgenden Überlegung: Wählen wir das erste Element unserer Sequenz als "aktuelles Ergebnis" aus; Behalten Sie es dann bei jeder Iteration bei oder verwerfen Sie es und wählen Sie ein neues Element als aktuell aus. Wir können die Wahrscheinlichkeit berechnen, dass ein bestimmtes Element am Ende als Produkt aller Wahrscheinlichkeiten ausgewählt wird, dass es in nachfolgenden Schritten nicht verworfen wird, mal die Wahrscheinlichkeit, dass es überhaupt ausgewählt wird. Wenn Sie rechnen, werden Sie feststellen, dass sich dieses Produkt auf (Gewicht des Elements) / (Summe aller Gewichte) vereinfacht, was genau das ist, was wir brauchen!

Da diese Methode die Eingabesequenz nur einmal durchläuft, funktioniert sie auch bei übermäßig großen Sequenzen, vorausgesetzt, die Summe der Gewichte passt in eine int(oder Sie können einen größeren Typ für diesen Zähler auswählen).

Keine Ursache
quelle
2
Ich würde dies vergleichen, bevor ich annehme, dass es besser ist, nur weil es einmal wiederholt wird. Genauso viele Zufallswerte zu generieren ist auch nicht gerade schnell.
Jean-Bernard Pellerin
1
@ Jean-Bernard Pellerin habe ich gemacht, und es ist eigentlich schneller auf großen Listen. Es sei denn, Sie verwenden einen kryptografisch starken Zufallsgenerator (-8
Nevermind
Sollte die akzeptierte Antwort imo sein. Mir gefällt dies besser als der Ansatz "Intervall" und "wiederholte Eingabe".
Vivin Paliath
2
Ich wollte nur sagen, dass ich in den letzten Jahren drei- oder viermal auf diesen Thread zurückgekommen bin, um diese Methode zu verwenden. Diese Methode hat es wiederholt geschafft, die Antworten, die ich für meine Zwecke benötige, schnell genug zu liefern. Ich wünschte, ich könnte diese Antwort jedes Mal, wenn ich zurückkomme, um sie zu benutzen, positiv bewerten.
Jim Yarbro
1
Schöne Lösung, wenn Sie sich wirklich nur einmal entscheiden müssen. Andernfalls ist es weitaus effizienter, die Vorbereitungen für die Lösung in der ersten Antwort einmal durchzuführen.
Deduplizierer
22

Bereits vorliegende Antworten sind gut und ich werde sie ein wenig erweitern.

Wie Benjamin vorschlug, werden bei dieser Art von Problem normalerweise kumulative Summen verwendet:

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

Um ein Element in dieser Struktur zu finden, können Sie einen Code wie Nevermind verwenden. Dieses Stück C # -Code, das ich normalerweise verwende:

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

Nun zum interessanten Teil. Wie effizient ist dieser Ansatz und welche Lösung ist am effizientesten? Mein Code benötigt O (n) Speicher und wird in O (n) Zeit ausgeführt. Ich glaube nicht, dass dies mit weniger als O (n) Raum getan werden kann, aber die zeitliche Komplexität kann viel geringer sein, O (log n) in der Tat. Der Trick besteht darin, eine binäre Suche anstelle einer regulären for-Schleife zu verwenden.

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

Es gibt auch eine Geschichte über das Aktualisieren von Gewichten. Im schlimmsten Fall bewirkt die Aktualisierung der Gewichtung für ein Element die Aktualisierung der kumulativen Summen für alle Elemente, wodurch die Aktualisierungskomplexität auf O (n) erhöht wird . Auch das kann mithilfe eines binär indizierten Baums auf O (log n) reduziert werden .

Kaiser Orionii
quelle
Guter Punkt über die binäre Suche
fl00r
Die Antwort von Nevermind benötigt keinen zusätzlichen Platz, daher ist sie O (1), erhöht jedoch die Laufzeitkomplexität, indem wiederholt Zufallszahlen generiert und die Wichtungsfunktion ausgewertet werden (was je nach zugrunde liegendem Problem kostspielig sein kann).
Benjamin Kloster
1
Was Sie für eine "besser lesbare Version" meines Codes halten, ist das eigentlich nicht. Ihr Code muss die Gesamtsumme der Gewichte und die kumulierten Summen im Voraus kennen. meins nicht.
Nevermind
@Benjamin Kloster Mein Code ruft die Gewichtsfunktion nur einmal pro Element auf - besser geht es nicht. Sie haben jedoch Recht mit Zufallszahlen.
Nevermind
@Nevermind: Sie rufen es nur einmal pro Aufruf der Auswahlfunktion auf. Wenn der Benutzer es also zweimal aufruft, wird die Wichtungsfunktion für jedes Element erneut aufgerufen. Natürlich könnten Sie es zwischenspeichern, aber dann sind Sie nicht mehr O (1) für die Raumkomplexität.
Benjamin Kloster
8

Dies ist eine einfache Python-Implementierung:

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

und

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

print select(population, weights)

In genetischen Algorithmen wird dieses Auswahlverfahren als Fitness-Proportional-Auswahl oder Roulette-Rad-Auswahl bezeichnet, da:

  • Ein Teil des Rades wird jeder der möglichen Auswahlen basierend auf ihrem Gewichtswert zugewiesen. Dies kann erreicht werden, indem das Gewicht einer Auswahl durch das Gesamtgewicht aller Auswahlen dividiert und auf 1 normiert wird.
  • Dann wird eine zufällige Auswahl getroffen, ähnlich wie das Roulette-Rad gedreht wird.

Auswahl an Rouletterädern

Typische Algorithmen haben die Komplexität O (N) oder O (log N), aber Sie können auch O (1) ausführen (z. B. Roulette-Rad-Auswahl über stochastische Akzeptanz ).

Manlio
quelle
Wissen Sie, aus welcher Quelle dieses Bild stammt? Ich möchte es für ein Papier verwenden, muss aber auf die Zuschreibung achten.
Malcolm MacLeod
@MalcolmMacLeod Entschuldigung, es wird in vielen GA-Artikeln / Websites verwendet, aber ich weiß nicht, wer der Autor ist.
Manlio
0

Dieser Kern tut genau das, wonach Sie fragen.

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

du kannst es so benutzen:

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

Der obige Code wird höchstwahrscheinlich (% 98) 0 zurückgeben, was der Index für 'apple' für das angegebene Array ist.

Außerdem testet dieser Code die oben bereitgestellte Methode:

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

Es gibt eine Ausgabe in etwa so:

Start...
Head count:52
Tails count:48
Ramazan POLAT
quelle
2
Bei Programmierern geht es um konzeptionelle Fragen, und von den Antworten wird erwartet, dass sie die Dinge erklären. Das Werfen von Code-Dumps anstelle von Erklärungen ist wie das Kopieren von Code von IDE auf Whiteboard: Es mag vertraut und manchmal sogar verständlich erscheinen, aber es fühlt sich seltsam an ... einfach seltsam. Whiteboard hat keinen Compiler
Mücke
Sie haben Recht, ich habe mich auf Code konzentriert und vergessen zu sagen, wie es funktioniert. Ich werde eine Erklärung hinzufügen, wie es funktioniert.
Ramazan Polat