Ich möchte zufällig ein Element aus einem Array auswählen, aber jedes Element hat eine bekannte Auswahlwahrscheinlichkeit.

Alle Chancen zusammen (innerhalb des Arrays) summieren sich zu 1.

Welchen Algorithmus würden Sie als den schnellsten und am besten geeigneten für große Berechnungen vorschlagen?

Beispiel:

id => chance
array[
    0 => 0.8
    1 => 0.2
]

Für diesen Pseudocode sollte der betreffende Algorithmus bei mehreren Aufrufen statistisch vier Elemente auf ID 0für ein Element auf ID zurückgeben 1.

Berechnen Sie die diskrete kumulative Dichtefunktion (CDF) Ihrer Liste - oder einfach ausgedrückt das Array der kumulativen Summen der Gewichte. Generieren Sie dann eine Zufallszahl im Bereich zwischen 0 und der Summe aller Gewichte (in Ihrem Fall möglicherweise 1), führen Sie eine binäre Suche durch, um diese Zufallszahl in Ihrem diskreten CDF-Array zu finden und den diesem Eintrag entsprechenden Wert zu erhalten ist Ihre gewichtete Zufallszahl.

Der Algorithmus ist einfach

rand_no = rand(0,1)
for each element in array 
     if(rand_num < element.probablity)
          select and break
     rand_num = rand_num - element.probability

Ich habe festgestellt, dass dieser Artikel am nützlichsten ist, um dieses Problem vollständig zu verstehen. Diese Stackoverflow-Frage ist möglicherweise auch das, wonach Sie suchen.

Ich glaube, die optimale Lösung ist die Verwendung der Alias-Methode (Wikipedia) . Es erfordert O (n) Zeit zum Initialisieren, O (1) Zeit zum Treffen einer Auswahl und O (n) Speicher.

Hier ist der Algorithmus zum Generieren des Ergebnisses des Würfelns eines gewichteten n- seitigen Chips (von hier aus ist es trivial, ein Element aus einem Array mit einer Länge von n auszuwählen ), wie aus diesem Artikel entnommen . Der Autor geht davon aus, dass Sie Funktionen zum Werfen eines fairen Würfels ( floor(random() * n)) und zum Werfen einer voreingenommenen Münze ( random() < p) haben.

Algorithmus: Voses Alias-Methode

Initialisierung:

1. Erstellen Sie Arrays Alias und Prob mit der Größe n .
2. Erstellen Sie zwei Arbeitslisten, Klein und Groß .
3. Multiplizieren Sie jede Wahrscheinlichkeit mit n .
4. Für jede skalierte Wahrscheinlichkeit p _i :
   1. Wenn p _i <1 ist , füge i zu Small hinzu .
   2. Andernfalls ( p _i ≥ 1 ) addiere i zu Large .
5. Während Small und Large nicht leer sind: ( Large wird möglicherweise zuerst geleert)
   1. Entfernen Sie das erste Element von Small . nenne es l .
   2. Entfernen Sie das erste Element von Large . nenne es g .
   3. Setze Prob [l] = p _l .
   4. Setze Alias ​​[l] = g .
   5. Setze p _g : = (p _g + p _l ) −1 . (Dies ist eine numerisch stabilere Option.)
   6. Wenn p _g <1 ist , füge g zu Small hinzu .
   7. Andernfalls ( p _g ≥ 1 ) addieren Sie g zu Large .
6. Während Large nicht leer ist:
   1. Entfernen Sie das erste Element von Large . nenne es g .
   2. Setze Prob [g] = 1 .
7. Während Small nicht leer ist: Dies ist nur aufgrund numerischer Instabilität möglich.
   1. Entfernen Sie das erste Element von Small . nenne es l .
   2. Setze Prob [l] = 1 .

Generation:

1. Erzeugen Sie einen fairen Würfelwurf aus einem n- seitigen Würfel. rufe die Seite i .
2. Wirf eine voreingenommene Münze, die mit der Wahrscheinlichkeit Prob [i] auftaucht .
3. Wenn die Münze "Köpfe" hochkommt, geben Sie i zurück .
4. Andernfalls geben Sie Alias ​​[i] zurück .

Ein weiteres Ruby-Beispiel:

def weighted_rand(weights = {})
  raise 'Probabilities must sum up to 1' unless weights.values.inject(&:+) == 1.0
  raise 'Probabilities must not be negative' unless weights.values.all? { |p| p >= 0 }
  # Do more sanity checks depending on the amount of trust in the software component using this method
  # E.g. don't allow duplicates, don't allow non-numeric values, etc.

  # Ignore elements with probability 0
  weights = weights.reject { |k, v| v == 0.0 }   # e.g. => {"a"=>0.4, "b"=>0.4, "c"=>0.2}

  # Accumulate probabilities and map them to a value
  u = 0.0
  ranges = weights.map { |v, p| [u += p, v] }   # e.g. => [[0.4, "a"], [0.8, "b"], [1.0, "c"]]

  # Generate a (pseudo-)random floating point number between 0.0(included) and 1.0(excluded)
  u = rand   # e.g. => 0.4651073966724186

  # Find the first value that has an accumulated probability greater than the random number u
  ranges.find { |p, v| p > u }.last   # e.g. => "b"
end

Wie benutzt man:

weights = {'a' => 0.4, 'b' => 0.4, 'c' => 0.2, 'd' => 0.0}

weighted_rand weights

Was ungefähr zu erwarten ist:

sample = 1000.times.map{ weighted_rand weights }
sample.count('a') # 396
sample.count('b') # 406
sample.count('c') # 198
sample.count('d') # 0

Ein Beispiel in Rubin

#each element is associated with its probability
a = {1 => 0.25 ,2 => 0.5 ,3 => 0.2, 4 => 0.05}

#at some point, convert to ccumulative probability
acc = 0
a.each { |e,w| a[e] = acc+=w }

#to select an element, pick a random between 0 and 1 and find the first   
#cummulative probability that's greater than the random number
r = rand
selected = a.find{ |e,w| w>r }

p selected[0]

Dies kann in O (1) erwarteter Zeit pro Probe wie folgt erfolgen.

Berechnen Sie die CDF F (i) für jedes Element i als die Summe der Wahrscheinlichkeiten kleiner oder gleich i.

Definieren Sie den Bereich r (i) eines Elements i als Intervall [F (i - 1), F (i)].

Erstellen Sie für jedes Intervall [(i - 1) / n, i / n] einen Bucket, der aus der Liste der Elemente besteht, deren Bereich das Intervall überlappt. Dies dauert insgesamt O (n) Zeit für das gesamte Array, solange Sie einigermaßen vorsichtig sind.

Wenn Sie das Array zufällig auswählen, berechnen Sie einfach, in welchem ​​Bucket sich die Zufallszahl befindet, und vergleichen es mit jedem Element der Liste, bis Sie das Intervall finden, in dem es enthalten ist.

Die Kosten einer Stichprobe betragen O (die erwartete Länge einer zufällig ausgewählten Liste) <= 2.

Dies ist ein PHP-Code, den ich in der Produktion verwendet habe:

/**
 * @return \App\Models\CdnServer
*/
protected function selectWeightedServer(Collection $servers)
{
    if ($servers->count() == 1) {
        return $servers->first();
    }

    $totalWeight = 0;

    foreach ($servers as $server) {
        $totalWeight += $server->getWeight();
    }

    // Select a random server using weighted choice
    $randWeight = mt_rand(1, $totalWeight);
    $accWeight = 0;

    foreach ($servers as $server) {
        $accWeight += $server->getWeight();

        if ($accWeight >= $randWeight) {
            return $server;
        }
    }
}

Rubinlösung mit dem Pickup Gem :

require 'pickup'

chances = {0=>80, 1=>20}
picker = Pickup.new(chances)

Beispiel:

5.times.collect {
  picker.pick(5)
}

gab Ausgabe:

[[0, 0, 0, 0, 0], 
 [0, 0, 0, 0, 0], 
 [0, 0, 0, 1, 1], 
 [0, 0, 0, 0, 0], 
 [0, 0, 0, 0, 1]]

Wenn das Array klein ist, würde ich dem Array eine Länge von in diesem Fall fünf geben und die entsprechenden Werte zuweisen:

array[
    0 => 0
    1 => 0
    2 => 0
    3 => 0
    4 => 1
]

Der Trick könnte darin bestehen, ein Hilfsarray mit Elementwiederholungen abzutasten, die die Wahrscheinlichkeit widerspiegeln

In Anbetracht der mit ihrer Wahrscheinlichkeit verbundenen Elemente als Prozentsatz:

h = {1 => 0.5, 2 => 0.3, 3 => 0.05, 4 => 0.05 }

auxiliary_array = h.inject([]){|memo,(k,v)| memo += Array.new((100*v).to_i,k) }   

ruby-1.9.3-p194 > auxiliary_array 
 => [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,                                 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4] 

auxiliary_array.sample

Wenn Sie so allgemein wie möglich sein möchten, müssen Sie den Multiplikator basierend auf der maximalen Anzahl von Bruchziffern berechnen und anstelle von 100 verwenden:

m = 10**h.values.collect{|e| e.to_s.split(".").last.size }.max

"Glücksrad" O (n), nur für kleine Arrays verwenden:

function pickRandomWeighted(array, weights) {
    var sum = 0;
    for (var i=0; i<weights.length; i++) sum += weights[i];
    for (var i=0, pick=Math.random()*sum; i<weights.length; i++, pick-=weights[i])
        if (pick-weights[i]<0) return array[i];
}

Ich würde mir vorstellen, dass Zahlen größer oder gleich 0,8, aber kleiner als 1,0 das dritte Element auswählen.

Mit anderen Worten:

x ist eine Zufallszahl zwischen 0 und 1

wenn 0,0> = x <0,2: Punkt 1

wenn 0,2> = x <0,8: Punkt 2

wenn 0,8> = x <1,0: Punkt 3

Ich werde die Antwort auf https://stackoverflow.com/users/626341/masciugo verbessern .

Grundsätzlich erstellen Sie ein großes Array, bei dem die Häufigkeit, mit der ein Element angezeigt wird, proportional zum Gewicht ist.

Es hat einige Nachteile.

1. Das Gewicht ist möglicherweise nicht ganzzahlig. Stellen Sie sich vor, Element 1 hat eine Wahrscheinlichkeit von pi und Element 2 hat eine Wahrscheinlichkeit von 1-pi. Wie teilt man das auf? Oder stellen Sie sich vor, es gibt Hunderte solcher Elemente.
2. Das erstellte Array kann sehr groß sein. Stellen Sie sich vor, wenn der kleinste gemeinsame Multiplikator 1 Million beträgt, benötigen wir ein Array mit 1 Million Elementen in dem Array, das wir auswählen möchten.

Um dem entgegenzuwirken, tun Sie Folgendes.

Erstellen Sie ein solches Array, fügen Sie jedoch nur zufällig ein Element ein. Die Wahrscheinlichkeit, dass ein Element eingefügt wird, ist proportional zum Gewicht.

Wählen Sie dann ein zufälliges Element aus dem Üblichen aus.

Wenn es also 3 Elemente mit unterschiedlichem Gewicht gibt, wählen Sie einfach ein Element aus einem Array von 1-3 Elementen aus.

Probleme können auftreten, wenn das konstruierte Element leer ist. Das heißt, es kommt einfach vor, dass keine Elemente im Array angezeigt werden, weil ihre Würfel unterschiedlich würfeln.

In diesem Fall schlage ich vor, dass die Wahrscheinlichkeit, mit der ein Element eingefügt wird, p (eingefügt) = wi / wmax ist.

Auf diese Weise wird ein Element eingefügt, nämlich das mit der höchsten Wahrscheinlichkeit. Die anderen Elemente werden durch die relative Wahrscheinlichkeit eingefügt.

Angenommen, wir haben 2 Objekte.

Element 1 wird in 0,20% der Fälle angezeigt. Element 2 zeigt 0,40% der Zeit und hat die höchste Wahrscheinlichkeit.

Im Bereich wird Element 2 ständig angezeigt. Element 1 wird die halbe Zeit angezeigt.

Element 2 wird also zweimal so oft wie Element 1 genannt. Der Allgemeinheit halber werden alle anderen Elemente proportional zu ihrem Gewicht genannt. Auch die Summe aller ihrer Wahrscheinlichkeiten ist 1, da das Array immer mindestens 1 Element hat.