Einzigartige (sich nicht wiederholende) Zufallszahlen in O(1)?

Question

Ich würde gerne eindeutige Zufallszahlen zwischen 0 und 1000 generieren, die sich nie wiederholen (d.h. 6 taucht nicht zweimal auf), aber dafür nicht auf so etwas wie eine O(N)-Suche der vorherigen Werte zurückgreifen. Ist dies möglich?

Answer 1

Initialisieren Sie ein Array von 1001 Ganzzahlen mit den Werten 0-1000 und setzen Sie eine Variable, max, auf den aktuellen Maximalindex des Arrays (beginnend mit 1000). Wählen Sie eine Zufallszahl, r, zwischen 0 und max, tauschen Sie die Zahl an der Position r mit der Zahl an der Position max und geben Sie die Zahl zurück, die jetzt an der Position max steht. Dekrementiere max um 1 und fahre fort. Wenn max gleich 0 ist, setzen Sie max zurück auf die Größe des Arrays - 1 und beginnen Sie erneut, ohne dass das Array neu initialisiert werden muss.

Aktualisierung: Obwohl ich bei der Beantwortung der Frage selbst auf diese Methode gekommen bin, habe ich nach einigen Nachforschungen festgestellt, dass es sich um eine modifizierte Version von Fisher-Yates bekannt als Durstenfeld-Fisher-Yates oder Knuth-Fisher-Yates. Da die Beschreibung vielleicht etwas schwierig zu verstehen ist, habe ich unten ein Beispiel angeführt (mit 11 statt 1001 Elementen):

Array beginnt mit 11 Elementen, die mit array[n] = n initialisiert sind, max beginnt bei 10:

+--+--+--+--+--+--+--+--+--+--+--+
| 0| 1| 2| 3| 4| 5| 6| 7| 8| 9|10|
+--+--+--+--+--+--+--+--+--+--+--+
                                ^
                               max    

Bei jeder Iteration wird eine Zufallszahl r zwischen 0 und max gewählt, array[r] und array[max] werden vertauscht, das neue array[max] wird zurückgegeben, und max wird dekrementiert:

max = 10, r = 3
           +--------------------+
           v                    v
+--+--+--+--+--+--+--+--+--+--+--+
| 0| 1| 2|10| 4| 5| 6| 7| 8| 9| 3|
+--+--+--+--+--+--+--+--+--+--+--+

max = 9, r = 7
                       +-----+
                       v     v
+--+--+--+--+--+--+--+--+--+--+--+
| 0| 1| 2|10| 4| 5| 6| 9| 8| 7: 3|
+--+--+--+--+--+--+--+--+--+--+--+

max = 8, r = 1
     +--------------------+
     v                    v
+--+--+--+--+--+--+--+--+--+--+--+
| 0| 8| 2|10| 4| 5| 6| 9| 1: 7| 3|
+--+--+--+--+--+--+--+--+--+--+--+

max = 7, r = 5
                 +-----+
                 v     v
+--+--+--+--+--+--+--+--+--+--+--+
| 0| 8| 2|10| 4| 9| 6| 5: 1| 7| 3|
+--+--+--+--+--+--+--+--+--+--+--+

...

Nach 11 Iterationen sind alle Zahlen im Array ausgewählt, max == 0, und die Arrayelemente werden neu gemischt:

+--+--+--+--+--+--+--+--+--+--+--+
| 4|10| 8| 6| 2| 0| 9| 5| 1| 7| 3|
+--+--+--+--+--+--+--+--+--+--+--+

An diesem Punkt kann max auf 10 zurückgesetzt werden und der Prozess kann fortgesetzt werden.

Answer 2

Sie können dies tun:

1. Erstellen Sie eine Liste, 0..1000.
2. Die Liste wird gemischt. (Siehe Fisher-Yates-Mischung für eine gute Möglichkeit, dies zu tun).
3. Rückgabe der Nummern in der Reihenfolge der gemischten Liste.

Dies erfordert also nicht jedes Mal eine Suche nach alten Werten, aber es erfordert immer noch O(N) für die anfängliche Umschichtung. Aber wie Nils in den Kommentaren bemerkte, wird dies mit O(1) amortisiert.

Answer 3

Verwenden Sie eine Maximal linear rückgekoppeltes Schieberegister .

Es ist in ein paar Zeilen C implementierbar und macht zur Laufzeit nicht viel mehr als ein paar Tests/Verzweigungen, ein wenig Addition und Bitverschiebung. Es ist nicht zufällig, aber es täuscht die meisten Leute.

Answer 4

Sie könnten verwenden Format-erhaltende Verschlüsselung um einen Zähler zu verschlüsseln. Ihr Zähler geht einfach von 0 aufwärts, und die Verschlüsselung verwendet einen Schlüssel Ihrer Wahl, um ihn in einen scheinbar zufälligen Wert mit beliebiger Radix und Breite zu verwandeln. Für das Beispiel in dieser Frage z. B.: Radix 10, Breite 3.

Blockchiffren haben normalerweise eine feste Blockgröße von z. B. 64 oder 128 Bit. Mit der Format-erhaltenden Verschlüsselung können Sie jedoch aus einer Standard-Chiffre wie AES eine Chiffre mit geringerer Breite machen, mit beliebiger Radix und Breite, mit einem Algorithmus, der immer noch kryptographisch robust ist.

Es gibt garantiert keine Kollisionen (da kryptografische Algorithmen eine 1:1-Zuordnung erstellen). Außerdem ist es umkehrbar (eine 2-Wege-Zuordnung), d. h. Sie können die resultierende Zahl nehmen und zu dem Zählerwert zurückkehren, mit dem Sie begonnen haben.

Diese Technik benötigt keinen Speicher, um ein gemischtes Array usw. zu speichern, was auf Systemen mit begrenztem Speicher ein Vorteil sein kann.

AES-FFX ist eine vorgeschlagene Standardmethode, um dies zu erreichen. Ich habe mit einigem grundlegenden Python-Code experimentiert, der auf der AES-FFX-Idee basiert, obwohl er nicht vollständig konform ist. siehe Python-Code hier . Es kann z. B. einen Zähler in eine zufällig aussehende 7-stellige Dezimalzahl oder eine 16-Bit-Zahl verschlüsseln. Hier ist ein Beispiel für Radix 10, Breite 3 (um eine Zahl zwischen 0 und 999 einschließlich zu erhalten), wie in der Frage angegeben:

000   733
001   374
002   882
003   684
004   593
005   578
006   233
007   811
008   072
009   337
010   119
011   103
012   797
013   257
014   932
015   433
...   ...

Um andere, sich nicht wiederholende Pseudo-Zufallsfolgen zu erhalten, ändern Sie den Verschlüsselungsschlüssel. Jeder Verschlüsselungscode erzeugt eine andere, sich nicht wiederholende Pseudo-Zufallsfolge.

Answer 5

Sie könnten A verwenden Linearer kongruenter Generator . Wo m (der Modulus) wäre die nächste Primzahl, die größer als 1000 ist. Wenn Sie eine Zahl außerhalb des Bereichs erhalten, nehmen Sie einfach die nächste. Die Folge wiederholt sich nur, wenn alle Elemente vorkommen, und Sie brauchen keine Tabelle zu verwenden. Beachten Sie jedoch die Nachteile dieses Generators (u. a. mangelnde Zufälligkeit).