Der effizienteste Algorithmus zum Drucken von 1-100 unter Verwendung eines bestimmten Zufallszahlengenerators

11

Wir erhalten einen Zufallszahlengenerator, RandNum50der gleichmäßig eine Zufallszahl im Bereich von 1 bis 50 erzeugt. Wir können nur diesen Zufallszahlengenerator verwenden, um alle Ganzzahlen von 1 bis 100 in zufälliger Reihenfolge zu generieren und zu drucken. Jede Zahl muss genau einmal kommen, und die Wahrscheinlichkeit, dass eine Zahl an einem beliebigen Ort auftritt, muss gleich sein.

Was ist der effizienteste Algorithmus dafür?

Raj Wadhwa
quelle
1
Verwenden Sie einen Array- oder Bitvektor, um die bereits gesehenen Zahlen aufzuzeichnen, und einen Zähler, um die Anzahl der gesehenen eindeutigen Zahlen aufzuzeichnen.
Dave Clarke
@ DaveClarke Wie kann ich damit eine Zahl größer als 50 generieren? Wenn ich es mehr als 1 Mal benutze, wie werde ich dann auch 1 damit generieren?
Raj Wadhwa
1
Die Herausforderung besteht natürlich darin, sicherzustellen, dass alle Orte mit gleicher Wahrscheinlichkeit auftreten. Sie könnten verwenden RandNum100 = (RandNum50() * 2) - (RandNum50 > 25) ? 0 : 1).
Dave Clarke
2
@ DaveClarke: Sie schlagen also eine iterierte Ablehnungsstichprobe vor? Das würde nur in Erwartung enden.
Raphael
Ich gab nur einen Hinweis.
Dave Clarke

Antworten:

3

Ich dachte (also kann es falsch sein :-) an diese -Lösung, die das Fisher-Yates-Shuffle verwendet . Um bei jeder Iteration eine gleichmäßige Verteilung mit guter Annäherung (siehe Abschnitt BEARBEITEN) zu erhalten, können Sie diesen Trick verwenden, um einen Wert zwischen 0 und k - 1 zu erzeugen :O(N2)krand0k- -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 hervorgehoben, krandliefert die obige Funktion keine wirklich gleichmäßige Verteilung. Es gibt andere Methoden, mit denen eine bessere (willkürlich bessere) und schnellere Annäherung erzielt werden kann. (meines Wissens) besteht die einzige Möglichkeit, eine wirklich gleichmäßige Verteilung zu erhalten, darin, die Ablehnungsstichprobe zu verwenden : Wählen Sie Zufallsbits, und wenn die erhaltene Zahl r kleiner als k ist, geben Sie sie zurück, andernfalls generieren Sie sie eine andere Zufallszahl; eine mögliche Implementierung:m=Log2(k)rk

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
    }
}
Vor
quelle
1
Die Wikipedia-Seite, auf die Sie verlinken, gibt an, dass es eine -Variante gibt. O(n)
Dave Clarke
1
Ich denke, "shuffle" ist hier das Schlüsselwort.
Raphael
4
Der Trick in krand (k) ergibt keine wirklich gleichmäßige Verteilung, obwohl dies eine gute Annäherung ist: Selbst für k = 3 ergibt sich eine Chance von 33,3333328%, 0 auszugeben. Gibt es hier eine Rechtfertigung für die Summierung bis zu k ? Ich würde denken, dass eine kleinere Grenze ausreicht, wenn wir nur eine Annäherung wollen.
Erick Wong
1
@ErickWong: du hast recht; Ich denke, dass die wahre Gleichverteilung nur mit der Ablehnungsstichprobenmethode erreicht werden kann, die nicht garantiert in konstanter Zeit endet. Es gibt andere Approximationsschemata (mit denen jede gewünschte Approximation erreicht werden kann). Das von mir vorgeschlagene ist das erste, das mir in den Sinn kam.
Vor dem
2
@ ex0du5: Ich weiß das, aber wie erzeugt man eine einheitliche Zufallspermutation von Zahlen [1..100] mit nur einem einheitlichen Zufallsgenerator in [1..100]? Die einzige alternative Methode, die ich kenne, ist: Schritt 1) ​​Wählen Sie einen Zufallswert in 1..100 ; Schritt 2) Wenn r bereits ausgewählt wurde, verwerfen Sie es und gehen Sie zu Schritt 1. Schritt 3) drucke r ; Schritt 4) Wenn wir nicht alle 100 Zahlen gedruckt haben, gehe zu Schritt 1. Diese Methode verschiebt die Zurückweisung jedoch einfach auf die bereits ausgewählten Elemente. r1..100rr
Vor dem
4

Wie wäre es mit einem Beweis, dass es keinen solchen Algorithmus gibt, der garantiert nur eine begrenzte Anzahl von RandNum50()Anrufen erfordert, da andere Leute ungefähre Lösungen und Lösungen angegeben haben, bei denen eine unbestimmte Anzahl von Abweichungen vorgenommen wird ?

Wie andere angemerkt haben, entspricht das Drucken der Zahlen von 1 bis 100 in zufälliger Reihenfolge dem Drucken einer zufälligen Permutation dieser Zahlen; es gibt 100! von diesen Permutationen, und daher muss jede bestimmte Permutation mit der Wahrscheinlichkeit ausgegeben werden1100!

kRandNum50kkRandNum50kkRandNum50(r1,r2,,rk)150kc50kc1100!100!50kk100!50k

Steven Stadnicki
quelle
2

nlogn+O(1)

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

1n!123n

Wenn Sie nicht wissen, wie Sie eine Uniform, wie in diesem Beitrag vorgeschlagen, aus einem zufälligen Bit generieren können, können Sie auf diese Weise auch direkt eine Annäherung der Uniform generieren (was Vor's "Trulyrand" entspricht, aber schneller ist):

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

P50PQ=Pmodnn=100!P>n

Jérémie
quelle
1

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

Dies "drückt" den Peak in der RandNum50() + RandNum50()Verteilung gleichmäßig nach vorne.

Ich bin mir ziemlich sicher, dass dies nicht ganz richtig ist, wie ich es angegeben habe, da der 0-Index (1) nicht von der ersten Wahl erhältlich ist und ich nicht schnell eine alternative 1..50 + 1..50-Anpassung sehen kann, die 0 ergibt ..99.

Aktualisieren

Um das von mir festgestellte Problem zu beheben, habe ich, RandNum100wie in den Fragenkommentaren erwähnt, den ersten kVersatz zufällig initialisiert .

Dies erzeugt eine Verteilung mit einer signifikanten Welle an der Vorderseite.

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

Testen von VB.NET-Code, bei dem ich sogar für K. gesorgt habe. Beachten Sie, dass es sich um O (K), 6K + 2 handelt.

Mark Hurd
quelle