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

Ich denke, dass Linearer kongruenter Generator wäre die einfachste Lösung.

und es gibt nur 3 Einschränkungen für den a , c y m Werte

1. m y c sind relativ primär,
2. a-1 ist teilbar durch alle Primfaktoren von m
3. a-1 ist teilbar durch 4 si m ist teilbar durch 4

PS Die Methode wurde bereits erwähnt, aber der Beitrag enthält falsche Annahmen über die konstanten Werte. Die folgenden Konstanten sollten für Ihren Fall gut funktionieren

In Ihrem Fall können Sie Folgendes verwenden a = 1002 , c = 757 , m = 1001

X = (1002 * X + 757) mod 1001

Answer 2

Für niedrige Zahlen wie 0...1000 ist es einfach, eine Liste zu erstellen, die alle Zahlen enthält, und diese zu mischen. Aber wenn die Menge der zu ziehenden Zahlen sehr groß ist, gibt es einen anderen eleganten Weg: Man kann eine pseudozufällige Permutation mit Hilfe eines Schlüssels und einer kryptografischen Hash-Funktion erstellen. Siehe den folgenden C++-ähnlichen Beispiel-Pseudocode:

unsigned randperm(string key, unsigned bits, unsigned index) {
  unsigned half1 =  bits    / 2;
  unsigned half2 = (bits+1) / 2;
  unsigned mask1 = (1 << half1) - 1;
  unsigned mask2 = (1 << half2) - 1;
  for (int round=0; round<5; ++round) {
    unsigned temp = (index >> half1);
    temp = (temp << 4) + round;
    index ^= hash( key + "/" + int2str(temp) ) & mask1;
    index = ((index & mask2) << half1) | ((index >> half2) & mask1);
  }
  return index;
}

Hier, hash ist einfach eine beliebige Pseudozufallsfunktion, die eine Zeichenkette auf eine möglicherweise große vorzeichenlose Ganzzahl abbildet. Die Funktion randperm ist eine Permutation aller Zahlen innerhalb 0...pow(2,bits)-1 unter der Annahme eines festen Schlüssels. Dies ergibt sich aus der Konstruktion, da jeder Schritt, der die Variable index ist reversibel. Dies ist inspiriert von einem Feistel-Chiffre .

Answer 3

Sie brauchen nicht einmal ein Array, um diese Aufgabe zu lösen.

Sie benötigen eine Bitmaske und einen Zähler.

Initialisieren Sie den Zähler auf Null und erhöhen Sie ihn bei aufeinanderfolgenden Aufrufen. XOR-Verknüpfung des Zählers mit der Bitmaske (beim Start zufällig ausgewählt oder fest), um eine Pseudo-Zufallszahl zu erzeugen. Wenn Sie keine Zahlen haben können, die größer als 1000 sind, verwenden Sie keine Bitmaske, die breiter als 9 Bit ist. (Mit anderen Worten, die Bitmaske ist eine ganze Zahl, die nicht größer als 511 ist).

Stellen Sie sicher, dass Sie den Zähler auf Null zurücksetzen, wenn er 1000 überschritten hat. Zu diesem Zeitpunkt können Sie eine andere zufällige Bitmaske auswählen - wenn Sie möchten -, um dieselbe Reihe von Zahlen in einer anderen Reihenfolge zu erzeugen.

Answer 4

Sie können meinen hier beschriebenen Xincrol-Algorithmus verwenden:

http://openpatent.blogspot.co.il/2013/04/xincrol-unique-and-random-number.html

Dies ist eine rein algorithmische Methode zur Erzeugung zufälliger, aber eindeutiger Zahlen ohne Arrays, Listen, Permutationen oder hohe CPU-Last.

Die neueste Version erlaubt es auch, den Zahlenbereich festzulegen. Wenn ich zum Beispiel eindeutige Zufallszahlen im Bereich von 0-1073741821 haben möchte.

Ich habe es praktisch benutzt für

• MP3-Player, der jeden Titel zufällig abspielt, aber nur einmal pro Album/Verzeichnis
• Pixelweise Überblendung von Videobildern (schnell und sanft)
• Erzeugen eines geheimen "Rausch"-Nebels über einem Bild für Signaturen und Markierungen (Steganografie)
• Data Object IDs für die Serialisierung von großen Mengen von Java-Objekten über Datenbanken
• Schutz von Triple Majority Speicherbits
• Adress+Wert-Verschlüsselung (jedes Byte wird nicht nur verschlüsselt, sondern auch an eine neue verschlüsselte Stelle im Puffer verschoben). Das hat die Kryptoanalytiker wirklich wütend auf mich gemacht :-)
• Plain Text to Plain Like Crypt Textverschlüsselung für SMS, E-Mails usw.
• Mein Texas Hold`em Poker-Rechner (THC)
• Mehrere meiner Spiele für Simulationen, "Shuffling", Ranking
• mehr

Sie ist offen und kostenlos. Probieren Sie es aus...

Answer 5

Diese Methode führt zu angemessenen Ergebnissen, wenn der Grenzwert hoch und Sie wollen nur ein paar Zufallszahlen erzeugen.

#!/usr/bin/perl

($top, $n) = @ARGV; # generate $n integer numbers in [0, $top)

$last = -1;
for $i (0 .. $n-1) {
    $range = $top - $n + $i - $last;
    $r = 1 - rand(1.0)**(1 / ($n - $i));
    $last += int($r * $range + 1);
    print "$last ($r)\n";
}

Beachten Sie, dass die Zahlen in aufsteigender Reihenfolge generiert werden, Sie können sie aber auch nachträglich mischen.