Wählen Sie ein zufälliges Array-Element, das eine bestimmte Eigenschaft erfüllt.

Question

Angenommen, ich habe eine Liste namens elements, von denen jede eine boolesche Eigenschaft erfüllt oder nicht erfüllt p. Ich möchte eines der Elemente auswählen, die zufällig mit gleichmäßiger Verteilung erfüllt. Ich weiß nicht im Voraus, wie viele Artikel diese Eigenschaft erfüllen .

Wird der folgende Code tun dies ?:

pickRandElement(elements, p) 
    randElement = null 
    count = 0 
    foreach element in elements 
      if (p(element)) 
       count = count + 1 
       if (randInt(count) == 0) 
        randElement = element 

    return randElement 

(randInt(n) gibt eine Zufalls int k mit 0 <= k < n.)

Answer 1

Es funktioniert mathematisch. Kann durch Induktion nachgewiesen werden.

Offensichtlich funktioniert für n = 1 Element, das p erfüllt.

Für n + 1 Elemente wählen wir das Element n + 1 mit der Wahrscheinlichkeit 1/(n + 1), also ist seine Wahrscheinlichkeit OK.Aber wie wirkt sich das auf die Endwahrscheinlichkeit aus, eines der früheren n Elemente auszuwählen?

hatte jeder nach dem Stand der n eine Chance, mit einer Wahrscheinlichkeit von 1/n ausgewählt ist, bis wir Element n + 1 gefunden. Jetzt, nach dem Finden von n + 1, gibt es eine 1/(n + 1) Chance, dass das Element n + 1 gewählt wird, so dass es eine Wahrscheinlichkeit von n/(n + 1) gibt, dass das vorher gewählte Element gewählt bleibt. Was bedeutet, dass seine letzte Wahrscheinlichkeit, nach n + 1 gefunden zu werden, 1/n * (n/n + 1) = 1/n + 1 ist - was die Wahrscheinlichkeit ist, die wir für alle n + 1 Elemente für eine gleichmäßige Verteilung wollen.

Wenn es für n = 1 funktioniert, und es funktioniert für n + 1 gegeben n, dann funktioniert es für alle n.

Answer 2

Ja, ich glaube schon.

Wenn Sie das erste Mal auf ein passendes Element stoßen, wählen Sie es auf jeden Fall. Beim nächsten Mal wählen Sie den neuen Wert mit einer Wahrscheinlichkeit von 1/2, so dass jedes der beiden Elemente eine gleiche Chance hat. In der folgenden Zeit wählen Sie den neuen Wert mit einer Wahrscheinlichkeit von 1/3 aus und lassen jedes der anderen Elemente mit einer Wahrscheinlichkeit von 1/2 * 2/3 = 1/3 zurück.

Ich versuche, einen Wikipedia-Artikel über diese Strategie zu finden, aber so weit ...

Beachten Sie, dass generell versagt, sind Sie nur eine Stichprobe aus einer Folge von unbekannter Länge Kommissionierung. Ihre Sequenz wird zufällig erzeugt, indem eine erste Sequenz genommen und gefiltert wird, aber der Algorithmus benötigt diesen Teil überhaupt nicht.

Ich dachte, ich einen LINQ-Operator in MoreLINQ bekommen hatte, dies zu tun, aber ich kann es nicht im Repository ... EDIT finden: Zum Glück, es besteht nach wie vor aus this answer:

public static T RandomElement<T>(this IEnumerable<T> source, 
           Random rng) 
{ 
    T current = default(T); 
    int count = 0; 
    foreach (T element in source) 
    { 
     count++; 
     if (rng.Next(count) == 0) 
     { 
      current = element; 
     }    
    } 
    if (count == 0) 
    { 
     throw new InvalidOperationException("Sequence was empty"); 
    } 
    return current; 
} 

Answer 3

Für der Übersichtlichkeit halber, ich würde versuchen:

pickRandElement(elements, p) 
    OrderedCollection coll = new OrderedCollection 
    foreach element in elements 
      if (p(element)) 
       coll.add(element) 
    if (coll.size == 0) return null 
    else return coll.get(randInt(coll.size)) 

Für mich, das macht es viel klarer, was Sie versuchen selbsterklärend zu tun und ist. Obendrein ist es einfacher und eleganter, und es ist jetzt offensichtlich, dass jeder mit einer gleichmäßigen Verteilung ausgewählt wird.

Answer 4

In Die Praxis der Programmierung, pg. 70, (Die Markov Chain-Algorithmus) gibt es einen ähnlichen Algorithmus dafür:.

[...] 
    nmatch = 0; 
    for (/* iterate list */) 
    if (rand() % ++nmatch == 0) /* prob = 1/nmatch */ 
     w = suf->word; 
[...] 

„den Algorithmus Hinweis für ein Element zufällig ausgewählt wird, wenn wir nicht wissen, wie viele Artikel gibt es die variable nmatch die Anzahl von Übereinstimmungen als die Liste zählt, wird abgetastet. der Ausdruck

rand() % ++nmatch == 0 

Inkrementen nmatch und dann wahr mit einer Wahrscheinlichkeit von 1/nmatch ist.“

Answer 5

decowboy hat einen schönen Beweis dafür, dass diese auf TopCoder