Effizientesten Algorithmus zum Drucken 1-100 mit einem gegebenen Zufallszahlengenerator

Question

Wir erhalten einen Zufallszahlengenerator RandNum50 Dies erzeugt eine zufällige Ganzzahl einheitlich im Bereich 1–50. Wir können nur diesen Zufallszahlengenerator verwenden, um alle Ganzzahlen in einer zufälligen Reihenfolge von 1 bis 100 zu generieren und zu drucken. Jede Zahl muss genau erfolgen, und die Wahrscheinlichkeit, dass eine Anzahl an jedem Ort auftritt, muss gleich sein.

Was ist der effizienteste Algorithmus dafür?

Answer 1

Ich dachte (also kann es falsch sein :-) von dieser $ o (n^2) $ -Lösung, die die verwendet Fisher-yates Shuffle. Um eine einheitliche Verteilung mit Gute Annäherung (Siehe Abschnitt Bearbeiten unten) Bei jeder Iteration können Sie diesen Trick verwenden, um einen Wert zu erzeugen krand zwischen 0 $ und $ K-1 $:

 // return a random number in [0..k-1] with uniform distribution
 // using a uniform random generator in [1..50]
 funtion krand(k) {    
   sum = 0
   for i = 1 to k do sum = sum + RandNum50() - 1
   krand = sum mod k
 }

Der Fisher-Yates-Algorithmus wird:

arr : array[0..99]
for i = 0  to 99 do arr[i] = i+1; // store 1..100 in the array
for i = 99 downto 1 {
  r = krand(i+1)  // random value in [0..i]
  exchange the values of arr[i] and arr[r]
}
for i = 0 to 99 do print arr[i]

BEARBEITEN:

Wie von Erick die krand Funktion oben gibt keine wirklich einheitliche Verteilung zurück. Es gibt andere Methoden, die verwendet werden können, um eine bessere (willkürlich bessere) und schnellere Annäherung zu erhalten. Aber (bis zu meinem Wissen) ist die einzige Möglichkeit, eine wirklich einheitliche Verteilung zu erhalten Ablehnungsabtastung: Wählen Sie $ m = lceil log_2 (k) rceil $ random Bits und wenn die Anzahl $ R $ erhalten ist, gilt es weniger als $ k $. eine mögliche Implementierung:

function trulyrand(k) {
    if (k <= 1) return 0
    while (true) { // ... if you're really unlucky ...
      m = ceil(log_2 (k) ) // calculate m such that k < 2^m
      r = 0  // will hold the random value
      while (m >= 0) {  // ... will add m bits        
        if ( rand50() > 25 ) then b = 1 else b = 0   // random bit
        r = r * 2 + b  // shift and add the random bit
        m = m - 1
      }      
      if (r < k) then return r  // we have 0<=r<2^m ; accept it, if r < k
    }
}

Answer 2

Da andere Leute ungefähre Lösungen und Lösungen gegeben haben, die unbestimmte Anzahl von Abweichungen einnehmen RandNum50() Anrufe?

Wie andere bemerkt haben, ist das Drucken der Zahlen von 1 bis 100 in zufälliger Reihenfolge gleichbedeutend mit dem Drucken einer zufälligen Permutation dieser Zahlen. Es gibt 100! Von diesen Permutationen und so muss eine bestimmte Permutation mit Wahrscheinlichkeit $ frac {1} {100!} $ ausgegeben werden.

Aber wenn wir wüssten, dass unser Algorithmus zu den meisten $ k $ -Nall an verwendet wird RandNum50 Für einige $ k $ konnten wir uns wie folgt argumentieren: Erstens polsteren wir die Berechnungspfade, die weniger als $ k $ Anrufe annehmen RandNum50 Um zusätzliche Dummy -Anrufe zu tätigen (dh Anrufe, bei denen der zurückgegebene Wert irrelevant ist), so dass alle Berechnungspfade genau $ k $ Anrufe tätigen. Jede gegebene Sequenz von $ k $ Ergebnissen aus unseren Aufrufen an RandNum50 Muss zu einer Ausgangspermutation führen, und so können wir eine "Ergebnistabelle" erstellen, die eine bestimmte Sequenz $ (r_1, r_2, ldots, r_k) $ $ $ $ $ $ $ erstellen kann. Da jedes dieser Ergebnisse gleich wahrscheinlich ist (jede von ihnen hat Wahrscheinlichkeit $ displaystyle frac {1} {50^k} $), muss die Wahrscheinlichkeit, eine bestimmte Permutation aus unserem Algorithmus herauszuholen frac {c} {50^k} $ für einige $ c $. Aber $ displayStyle frac {1} {100!} $ Kann nicht von diesem Formular sein, denn $ 100! $ Teil Teilen Sie eine beliebige Anzahl des Formulars $ 50^k $). Dies bedeutet, dass keine mögliche Verteilung der Ergebnisse auf Zufallsnummer-Anrufe eine einheitliche Permutation erzeugen kann.

Answer 3

Die vorherigen Lösungen sind nicht optimal. Die Komplexität beträgt genau $ N log n + o (1) $ in Aufrufen nach Randnum50 und wird ausführlich beschrieben hier, Verwenden Sie als Quelle für Zufallsbit (wie von VOR vorgeschlagen):

if ( rand50() > 25 ) then b = 1 else b = 0   // random bit

Die Grundidee ist, dass Sie viele Teile sparen, wenn Sie eine Uniform zwischen 1 $ und $ N! $ Generieren und dann verwenden faktorielle Basiszerlegung, Anstatt eine Abfolge von Uniformen zu generieren, reichte bis zu 1 $ $, dann $ 2 $, dann 3 $ $ usw., $ n $. Dies ist, wie ich in der Post erwähne, das Thema eines Papiers, das ich eingereicht habe!

Wenn Sie nicht wissen, wie Sie eine Uniform erzeugen können, wie in diesem Beitrag vorgeschlagen, können Sie auf diese Weise auch eine Annäherung an die Uniform direkt erzeugen (was VORs "Trulyrand" entspricht, aber schneller):

P = (RandNum50()-1) + (RandNum50()-1)*50^1 + (RandNum50()-1)*50^2 + ...

Gehen Sie so weit, wie Sie gehen müssen. Dies entwickelt $ P $ in Basis $ 50 $. Dann einfach $ p $, dh, $ q = p mod n $, in Ihrem Fall $ n = 100! $. Dieser Wert ist nicht vollständig zufällig, aber ein Maß für die Einheitlichkeit, die häufig verwendet wird. Oder, wie VOR schon sagt, können Sie ablehnen, ob $ p> n $. Dann können Sie mit diesem Wert die faktorielle Basisausweitung durchführen, wie in der beschrieben Post.

Answer 4

Ich habe die Analyse nicht durchgeführt, um zu bestätigen, wie einheitlich (oder nicht) dies sein würde, und sie könnte ein echtes Shuffle angepasst werden, aber könnten Sie nur wählen, aus einem Startarray von der iTH INDEX = i + 1, das (k + RandNum50() + RandNum50() - 1) mod (100 - k) Index mit Entfernung für k = 0..99?

Dies "drückt" den Peak in der RandNum50() + RandNum50() Verbreitung gleichmäßig vorwärts.

_{Ich bin mir ziemlich sicher, dass dies nicht ganz richtig ist, wie ich es angegeben habe, da der 0 -Index (1) aus der ersten Wahl nicht erhältlich ist und ich keine alternative 1..50 + 1..50 -Einstellung sehen kann, die 0 erzeugt ..99.}

Aktualisieren

Um das von mir festgestellte Problem zu beheben, habe ich effektiv verwendet RandNum100 Wie in den Fragen erwähnt, Kommentare, um die erste zufällig zu initialisieren k Offset.

Dies erzeugt eine Verteilung mit einer signifikanten Welle vorne.

Anstatt um 1 voranzukommen, benutzte ich einen anderen RandNum50 das zuerst erhöhen k. Dies führt zu einem Ergebnis, das für mich zufällig genug ist, aber es ist immer noch nicht "wirklich" zufällig, wie leicht zu erkennen ist, wenn Sie K auf 2 ändern.

Testen von VB.NET -Code Wo ich mich für eine gleichmäßige K. beachten, ist es o (k), 6k+2 in der Tat.