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

Ich möchte eindeutige Zufallszahlen zwischen 0 und 1000 generieren, die sich nie wiederholen (dh 6 wird nicht zweimal angezeigt), aber dazu wird nicht auf eine O (N) -Suche nach vorherigen Werten zurückgegriffen. Ist das möglich?

Initialisieren Sie ein Array mit 1001 Ganzzahlen mit den Werten 0-1000 und setzen Sie eine Variable max auf den aktuellen Max-Index 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 aus und geben Sie die Zahl jetzt an der Position max zurück. Dekrementiere max um 1 und fahre fort. Wenn max 0 ist, setzen Sie max wieder auf die Größe des Arrays - 1 und starten Sie erneut, ohne dass das Array neu initialisiert werden muss.

Update: Obwohl ich diese Methode bei der Beantwortung der Frage selbst entwickelt habe, stelle ich nach einigen Recherchen fest, dass es sich um eine modifizierte Version von Fisher-Yates handelt, die als Durstenfeld-Fisher-Yates oder Knuth-Fisher-Yates bekannt ist. Da die Beschreibung möglicherweise etwas schwierig zu befolgen ist, habe ich nachfolgend ein Beispiel angegeben (mit 11 Elementen anstelle von 1001):

Das Array beginnt mit 11 Elementen, die mit Array [n] = n initialisiert wurden. Max beginnt mit 10:

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

Bei jeder Iteration wird eine Zufallszahl r zwischen 0 und max ausgewählt, Array [r] und Array [max] werden ausgetauscht, 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 wurden alle Zahlen im Array ausgewählt, max == 0, und die Array-Elemente werden gemischt:

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

Zu diesem Zeitpunkt kann max auf 10 zurückgesetzt werden und der Vorgang kann fortgesetzt werden.

Du kannst das:

1. Erstellen Sie eine Liste, 0..1000.
2. Mische die Liste. ( Eine gute Möglichkeit hierfür finden Sie unter Fisher-Yates-Shuffle .)
3. Geben Sie die Nummern in der Reihenfolge aus der gemischten Liste zurück.

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

Verwenden Sie ein Schieberegister für die maximale lineare Rückkopplung .

Es ist in ein paar Zeilen C implementierbar und führt zur Laufzeit kaum mehr als ein paar Tests / Verzweigungen, ein wenig Addition und Bitverschiebung durch. Es ist nicht zufällig, aber es täuscht die meisten Menschen.

Sie können einen linearen Kongruenzgenerator verwenden . Wobei m(der Modul) die nächste Primzahl ist, die größer als 1000 ist. Wenn Sie eine Zahl außerhalb des Bereichs erhalten, erhalten Sie einfach die nächste. Die Sequenz wird erst wiederholt, wenn alle Elemente aufgetreten sind und Sie keine Tabelle verwenden müssen. Beachten Sie jedoch die Nachteile dieses Generators (einschließlich mangelnder Zufälligkeit).

Sie können die formaterhaltende Verschlüsselung verwenden , um einen Zähler zu verschlüsseln. Ihr Zähler geht nur von 0 aufwärts und die Verschlüsselung verwendet einen Schlüssel Ihrer Wahl, um ihn in einen scheinbar zufälligen Wert mit dem gewünschten Radix und der gewünschten Breite umzuwandeln. ZB für das Beispiel in dieser Frage: Radix 10, Breite 3.

Blockchiffren haben normalerweise eine feste Blockgröße von zB 64 oder 128 Bit. Mit der formaterhaltenden Verschlüsselung können Sie jedoch eine Standardverschlüsselung wie AES verwenden und mit einem Algorithmus, der immer noch kryptografisch robust ist, eine Verschlüsselung mit kleinerer Breite erstellen, unabhängig von der gewünschten Größe und Breite.

Es wird garantiert nie zu Kollisionen kommen (da kryptografische Algorithmen eine 1: 1-Zuordnung erstellen). Es ist auch reversibel (eine 2-Wege-Zuordnung), sodass Sie die resultierende Zahl nehmen und zu dem Zählerwert zurückkehren können, mit dem Sie begonnen haben.

Diese Technik benötigt keinen Speicher zum Speichern eines gemischten Arrays usw., was auf Systemen mit begrenztem Speicher von Vorteil sein kann.

AES-FFX ist eine vorgeschlagene Standardmethode, um dies zu erreichen. Ich habe mit grundlegendem Python-Code experimentiert, der auf der AES-FFX-Idee basiert, obwohl er nicht vollständig konform ist - siehe Python-Code hier . Es kann beispielsweise einen Zähler mit einer zufällig aussehenden 7-stelligen Dezimalzahl oder einer 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 geben), 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
...   ...

Ändern Sie den Verschlüsselungsschlüssel, um verschiedene sich nicht wiederholende Pseudozufallssequenzen zu erhalten. Jeder Verschlüsselungsschlüssel erzeugt eine andere nicht wiederholte Pseudozufallssequenz.

Bei niedrigen Zahlen wie 0 ... 1000 ist es einfach, eine Liste mit allen Zahlen zu erstellen und zu mischen. Wenn die Anzahl der zu zeichnenden Zahlen jedoch sehr groß ist, gibt es eine andere elegante Möglichkeit: Sie können eine pseudozufällige Permutation mithilfe eines Schlüssels und einer kryptografischen Hash-Funktion erstellen. Siehe den folgenden C ++ - 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 hashist nur eine beliebige Pseudozufallsfunktion, die eine Zeichenfolge einer möglicherweise großen vorzeichenlosen Ganzzahl zuordnet. Die Funktion randpermist eine Permutation aller Zahlen innerhalb von 0 ... pow (2, Bits) -1 unter der Annahme eines festen Schlüssels. Dies folgt aus der Konstruktion, da jeder Schritt, der die Variable ändert, indexreversibel ist. Dies ist inspiriert von einer Feistel-Chiffre .

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 zum Generieren von zufälligen, aber eindeutigen Zahlen ohne Arrays, Listen, Permutationen oder hohe CPU-Auslastung.

In der neuesten Version können Sie auch den Zahlenbereich festlegen, z. B. wenn ich eindeutige Zufallszahlen im Bereich von 0-1073741821 möchte.

Ich habe es praktisch benutzt

• MP3-Player, der jedes Lied zufällig wiedergibt, jedoch nur einmal pro Album / Verzeichnis
• Pixelweiser Auflösungseffekt von Videobildern (schnell und flüssig)
• Erstellen eines geheimen "Rauschnebels" über dem Bild für Signaturen und Markierungen (Steganographie)
• Datenobjekt-IDs zur Serialisierung einer großen Anzahl von Java-Objekten über Datenbanken
• Schutz der Speicherbits mit dreifacher Mehrheit
• Adress + Wert-Verschlüsselung (jedes Byte wird nicht nur verschlüsselt, sondern auch an einen neuen verschlüsselten Speicherort im Puffer verschoben). Das hat Kryptoanalyse-Leute wirklich sauer auf mich gemacht :-)
• Plain Text to Plain Like Crypt Text-Verschlüsselung für SMS, E-Mails usw.
• Mein Texas Hold'em Poker Rechner (THC)
• Einige meiner Spiele für Simulationen, "Mischen", Rangliste
• Mehr

Es ist offen, kostenlos. Versuche es...

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

Du brauchst eine Bitmaske und einen Zähler.

Initialisieren Sie den Zähler auf Null und erhöhen Sie ihn bei aufeinanderfolgenden Aufrufen. XOR den Zähler mit der Bitmaske (zufällig beim Start ausgewählt oder fest), um eine Pseudozufallszahl zu generieren. Wenn Sie keine Zahlen haben können, die 1000 überschreiten, verwenden Sie keine Bitmaske, die breiter als 9 Bit ist. (Mit anderen Worten, die Bitmaske ist eine Ganzzahl, die nicht über 511 liegt.)

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

Ich denke, dass linearer Kongruenzgenerator die einfachste Lösung wäre.

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

1. m und c sind relativ prim,
2. a-1 ist durch alle Primfaktoren von m teilbar
3. a-1 ist teilbar durch 4 wenn m durch teilbar ist 4

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

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

X = (1002 * X + 757) mod 1001

Hier ist ein Code, den ich eingegeben habe und der die Logik der ersten Lösung verwendet. Ich weiß, dass dies "sprachunabhängig" ist, wollte dies aber nur als Beispiel in C # präsentieren, falls jemand nach einer schnellen praktischen Lösung sucht.

// Initialize variables
Random RandomClass = new Random();
int RandArrayNum;
int MaxNumber = 10;
int LastNumInArray;
int PickedNumInArray;
int[] OrderedArray = new int[MaxNumber];      // Ordered Array - set
int[] ShuffledArray = new int[MaxNumber];     // Shuffled Array - not set

// Populate the Ordered Array
for (int i = 0; i < MaxNumber; i++)                  
{
    OrderedArray[i] = i;
    listBox1.Items.Add(OrderedArray[i]);
}

// Execute the Shuffle                
for (int i = MaxNumber - 1; i > 0; i--)
{
    RandArrayNum = RandomClass.Next(i + 1);         // Save random #
    ShuffledArray[i] = OrderedArray[RandArrayNum];  // Populting the array in reverse
    LastNumInArray = OrderedArray[i];               // Save Last Number in Test array
    PickedNumInArray = OrderedArray[RandArrayNum];  // Save Picked Random #
    OrderedArray[i] = PickedNumInArray;             // The number is now moved to the back end
    OrderedArray[RandArrayNum] = LastNumInArray;    // The picked number is moved into position
}

for (int i = 0; i < MaxNumber; i++)                  
{
    listBox2.Items.Add(ShuffledArray[i]);
}

Diese Methodenergebnisse sind geeignet, wenn das Limit hoch ist und Sie nur wenige Zufallszahlen generieren möchten.

#!/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 jedoch anschließend mischen.

Sie könnten einen guten Pseudozufallszahlengenerator verwenden mit 10 Bits verwenden und 1001 bis 1023 wegwerfen, wobei 0 bis 1000 übrig bleiben.

Von hier bekommen wir das Design für ein 10 Bit PRNG ..

• 10 Bits, Rückkopplungspolynom x ^ 10 + x ^ 7 + 1 (Periode 1023)

• Verwenden Sie einen Galois LFSR, um schnellen Code zu erhalten

public static int[] randN(int n, int min, int max)
{
    if (max <= min)
        throw new ArgumentException("Max need to be greater than Min");
    if (max - min < n)
        throw new ArgumentException("Range needs to be longer than N");

    var r = new Random();

    HashSet<int> set = new HashSet<int>();

    while (set.Count < n)
    {
        var i = r.Next(max - min) + min;
        if (!set.Contains(i))
            set.Add(i);
    }

    return set.ToArray();
}

N Nicht wiederholte Zufallszahlen weisen je nach Bedarf eine Komplexität von O (n) auf.
Hinweis: Random sollte statisch sein, wobei die Gewindesicherheit angewendet wird.

Angenommen, Sie möchten die gemischten Listen immer wieder durchgehen, ohne die O(n)Verzögerung jedes Mal zu haben, wenn Sie neu beginnen, um sie erneut zu mischen. In diesem Fall können wir Folgendes tun:

1. Erstellen Sie 2 Listen A und B mit 0 bis 1000 nimmt 2nPlatz ein.

2. Das Mischen der Liste A mit Fisher-Yates braucht nZeit.

3. Wenn Sie eine Zahl zeichnen, mischen Sie in einem Schritt Fisher-Yates auf der anderen Liste.

4. Wenn sich der Cursor am Listenende befindet, wechseln Sie zur anderen Liste.

Vorverarbeitung

cursor = 0

selector = A
other    = B

shuffle(A)

Zeichnen

temp = selector[cursor]

swap(other[cursor], other[random])

if cursor == N
then swap(selector, other); cursor = 0
else cursor = cursor + 1

return temp

Die Frage Wie generieren Sie effizient eine Liste von K nicht wiederholenden ganzen Zahlen zwischen 0 und einer Obergrenze N. wird als Duplikat verknüpft - und wenn Sie etwas möchten, das O (1) pro generierter Zufallszahl ist (ohne O (n)) Startkosten)) Es gibt eine einfache Änderung der akzeptierten Antwort.

Erstellen Sie eine leere ungeordnete Karte (eine leere geordnete Karte benötigt O (log k) pro Element) von Ganzzahl zu Ganzzahl - anstatt ein initialisiertes Array zu verwenden. Setzen Sie max auf 1000, wenn dies das Maximum ist.

1. Wählen Sie eine Zufallszahl r zwischen 0 und max.
2. Stellen Sie sicher, dass beide Kartenelemente r und max in der ungeordneten Karte vorhanden sind. Wenn sie nicht vorhanden sind, erstellen Sie sie mit einem Wert, der ihrem Index entspricht.
3. Tauschelemente r und max
4. Geben Sie das Element max zurück und dekrementieren Sie max um 1 (wenn max negativ wird, sind Sie fertig).
5. Zurück zu Schritt 1.

Der einzige Unterschied zur Verwendung eines initialisierten Arrays besteht darin, dass die Initialisierung von Elementen verschoben / übersprungen wird - es werden jedoch genau dieselben Zahlen aus demselben PRNG generiert.

Eine andere Möglichkeit:

Sie können ein Array von Flags verwenden. Und nimm den nächsten, wenn er bereits ausgewählt ist.

Aber Vorsicht nach 1000 Aufrufen, die Funktion wird niemals enden, daher müssen Sie eine Schutzmaßnahme treffen.

Hier ist ein Beispiel für einen COBOL-Code, mit dem Sie herumspielen können.
Ich kann Ihnen die Datei RANDGEN.exe senden, damit Sie damit spielen können, um zu sehen, ob Sie es wollen.

   IDENTIFICATION DIVISION.
   PROGRAM-ID.  RANDGEN as "ConsoleApplication2.RANDGEN".
   AUTHOR.  Myron D Denson.
   DATE-COMPILED.
  * ************************************************************** 
  *  SUBROUTINE TO GENERATE RANDOM NUMBERS THAT ARE GREATER THAN
  *    ZERO AND LESS OR EQUAL TO THE RANDOM NUMBERS NEEDED WITH NO
  *    DUPLICATIONS.  (CALL "RANDGEN" USING RANDGEN-AREA.)
  *     
  *  CALLING PROGRAM MUST HAVE A COMPARABLE LINKAGE SECTION
  *    AND SET 3 VARIABLES PRIOR TO THE FIRST CALL IN RANDGEN-AREA     
  *
  *    FORMULA CYCLES THROUGH EVERY NUMBER OF 2X2 ONLY ONCE. 
  *    RANDOM-NUMBERS FROM 1 TO RANDOM-NUMBERS-NEEDED ARE CREATED 
  *    AND PASSED BACK TO YOU.
  *
  *  RULES TO USE RANDGEN:
  *
  *    RANDOM-NUMBERS-NEEDED > ZERO 
  *     
  *    COUNT-OF-ACCESSES MUST = ZERO FIRST TIME CALLED.
  *         
  *    RANDOM-NUMBER = ZERO, WILL BUILD A SEED FOR YOU
  *    WHEN COUNT-OF-ACCESSES IS ALSO = 0 
  *     
  *    RANDOM-NUMBER NOT = ZERO, WILL BE NEXT SEED FOR RANDGEN
  *    (RANDOM-NUMBER MUST BE <= RANDOM-NUMBERS-NEEDED)       
  *     
  *    YOU CAN PASS RANDGEN YOUR OWN RANDOM-NUMBER SEED
  *     THE FIRST TIME YOU USE RANDGEN.
  *     
  *    BY PLACING A NUMBER IN RANDOM-NUMBER FIELD
  *      THAT FOLLOWES THESE SIMPLE RULES:
  *        IF COUNT-OF-ACCESSES = ZERO AND 
  *        RANDOM-NUMBER > ZERO AND 
  *        RANDOM-NUMBER <= RANDOM-NUMBERS-NEEDED
  *       
  *    YOU CAN LET RANDGEN BUILD A SEED FOR YOU
  *     
  *      THAT FOLLOWES THESE SIMPLE RULES:
  *        IF COUNT-OF-ACCESSES = ZERO AND 
  *        RANDOM-NUMBER = ZERO AND 
  *        RANDOM-NUMBER-NEEDED > ZERO  
  *         
  *     TO INSURING A DIFFERENT PATTERN OF RANDOM NUMBERS
  *        A LOW-RANGE AND HIGH-RANGE IS USED TO BUILD
  *        RANDOM NUMBERS.
  *        COMPUTE LOW-RANGE =
  *             ((SECONDS * HOURS * MINUTES * MS) / 3).         
  *        A HIGH-RANGE = RANDOM-NUMBERS-NEEDED + LOW-RANGE
  *        AFTER RANDOM-NUMBER-BUILT IS CREATED 
  *        AND IS BETWEEN LOW AND HIGH RANGE
  *        RANDUM-NUMBER = RANDOM-NUMBER-BUILT - LOW-RANGE
  *               
  * **************************************************************         
   ENVIRONMENT DIVISION.
   INPUT-OUTPUT SECTION.
   FILE-CONTROL.
   DATA DIVISION.
   FILE SECTION.
   WORKING-STORAGE SECTION.
   01  WORK-AREA.
       05  X2-POWER                     PIC 9      VALUE 2. 
       05  2X2                          PIC 9(12)  VALUE 2 COMP-3.
       05  RANDOM-NUMBER-BUILT          PIC 9(12)  COMP.
       05  FIRST-PART                   PIC 9(12)  COMP.
       05  WORKING-NUMBER               PIC 9(12)  COMP.
       05  LOW-RANGE                    PIC 9(12)  VALUE ZERO.
       05  HIGH-RANGE                   PIC 9(12)  VALUE ZERO.
       05  YOU-PROVIDE-SEED             PIC X      VALUE SPACE.
       05  RUN-AGAIN                    PIC X      VALUE SPACE.
       05  PAUSE-FOR-A-SECOND           PIC X      VALUE SPACE.   
   01  SEED-TIME.
       05  HOURS                        PIC 99.
       05  MINUTES                      PIC 99.
       05  SECONDS                      PIC 99.
       05  MS                           PIC 99. 
  *
  * LINKAGE SECTION.
  *  Not used during testing  
   01  RANDGEN-AREA.
       05  COUNT-OF-ACCESSES            PIC 9(12) VALUE ZERO.
       05  RANDOM-NUMBERS-NEEDED        PIC 9(12) VALUE ZERO.
       05  RANDOM-NUMBER                PIC 9(12) VALUE ZERO.
       05  RANDOM-MSG                   PIC X(60) VALUE SPACE.
  *    
  * PROCEDURE DIVISION USING RANDGEN-AREA.
  * Not used during testing 
  *  
   PROCEDURE DIVISION.
   100-RANDGEN-EDIT-HOUSEKEEPING.
       MOVE SPACE TO RANDOM-MSG. 
       IF RANDOM-NUMBERS-NEEDED = ZERO
         DISPLAY 'RANDOM-NUMBERS-NEEDED ' NO ADVANCING
         ACCEPT RANDOM-NUMBERS-NEEDED.
       IF RANDOM-NUMBERS-NEEDED NOT NUMERIC 
         MOVE 'RANDOM-NUMBERS-NEEDED NOT NUMERIC' TO RANDOM-MSG
           GO TO 900-EXIT-RANDGEN.
       IF RANDOM-NUMBERS-NEEDED = ZERO
         MOVE 'RANDOM-NUMBERS-NEEDED = ZERO' TO RANDOM-MSG
           GO TO 900-EXIT-RANDGEN.
       IF COUNT-OF-ACCESSES NOT NUMERIC
         MOVE 'COUNT-OF-ACCESSES NOT NUMERIC' TO RANDOM-MSG
           GO TO 900-EXIT-RANDGEN.
       IF COUNT-OF-ACCESSES GREATER THAN RANDOM-NUMBERS-NEEDED
         MOVE 'COUNT-OF-ACCESSES > THAT RANDOM-NUMBERS-NEEDED'
           TO RANDOM-MSG
           GO TO 900-EXIT-RANDGEN.
       IF YOU-PROVIDE-SEED = SPACE AND RANDOM-NUMBER = ZERO
         DISPLAY 'DO YOU WANT TO PROVIDE SEED  Y OR N: '
           NO ADVANCING
           ACCEPT YOU-PROVIDE-SEED.  
       IF RANDOM-NUMBER = ZERO AND
          (YOU-PROVIDE-SEED = 'Y' OR 'y')
         DISPLAY 'ENTER SEED ' NO ADVANCING
         ACCEPT RANDOM-NUMBER. 
       IF RANDOM-NUMBER NOT NUMERIC
         MOVE 'RANDOM-NUMBER NOT NUMERIC' TO RANDOM-MSG
         GO TO 900-EXIT-RANDGEN.
   200-RANDGEN-DATA-HOUSEKEEPING.      
       MOVE FUNCTION CURRENT-DATE (9:8) TO SEED-TIME.
       IF COUNT-OF-ACCESSES = ZERO
         COMPUTE LOW-RANGE =
                ((SECONDS * HOURS * MINUTES * MS) / 3).
       COMPUTE RANDOM-NUMBER-BUILT = RANDOM-NUMBER + LOW-RANGE.  
       COMPUTE HIGH-RANGE = RANDOM-NUMBERS-NEEDED + LOW-RANGE.
       MOVE X2-POWER TO 2X2.             
   300-SET-2X2-DIVISOR.
       IF 2X2 < (HIGH-RANGE + 1) 
          COMPUTE 2X2 = 2X2 * X2-POWER
           GO TO 300-SET-2X2-DIVISOR.    
  * *********************************************************         
  *  IF FIRST TIME THROUGH AND YOU WANT TO BUILD A SEED.    *
  * ********************************************************* 
       IF COUNT-OF-ACCESSES = ZERO AND RANDOM-NUMBER = ZERO
          COMPUTE RANDOM-NUMBER-BUILT =
                ((SECONDS * HOURS * MINUTES * MS) + HIGH-RANGE).
       IF COUNT-OF-ACCESSES = ZERO        
         DISPLAY 'SEED TIME ' SEED-TIME 
               ' RANDOM-NUMBER-BUILT ' RANDOM-NUMBER-BUILT 
               ' LOW-RANGE  ' LOW-RANGE.          
  * *********************************************     
  *    END OF BUILDING A SEED IF YOU WANTED TO  * 
  * *********************************************               
  * ***************************************************
  * THIS PROCESS IS WHERE THE RANDOM-NUMBER IS BUILT  *  
  * ***************************************************   
   400-RANDGEN-FORMULA.
       COMPUTE FIRST-PART = (5 * RANDOM-NUMBER-BUILT) + 7.
       DIVIDE FIRST-PART BY 2X2 GIVING WORKING-NUMBER 
         REMAINDER RANDOM-NUMBER-BUILT. 
       IF RANDOM-NUMBER-BUILT > LOW-RANGE AND
          RANDOM-NUMBER-BUILT < (HIGH-RANGE + 1)
         GO TO 600-RANDGEN-CLEANUP.
       GO TO 400-RANDGEN-FORMULA.
  * *********************************************     
  *    GOOD RANDOM NUMBER HAS BEEN BUILT        *               
  * *********************************************
   600-RANDGEN-CLEANUP.
       ADD 1 TO COUNT-OF-ACCESSES.
       COMPUTE RANDOM-NUMBER = 
            RANDOM-NUMBER-BUILT - LOW-RANGE. 
  * *******************************************************
  * THE NEXT 3 LINE OF CODE ARE FOR TESTING  ON CONSOLE   *  
  * *******************************************************
       DISPLAY RANDOM-NUMBER.
       IF COUNT-OF-ACCESSES < RANDOM-NUMBERS-NEEDED
        GO TO 100-RANDGEN-EDIT-HOUSEKEEPING.     
   900-EXIT-RANDGEN.
       IF RANDOM-MSG NOT = SPACE
        DISPLAY 'RANDOM-MSG: ' RANDOM-MSG.
        MOVE ZERO TO COUNT-OF-ACCESSES RANDOM-NUMBERS-NEEDED RANDOM-NUMBER. 
        MOVE SPACE TO YOU-PROVIDE-SEED RUN-AGAIN.
       DISPLAY 'RUN AGAIN Y OR N '
         NO ADVANCING.
       ACCEPT RUN-AGAIN.
       IF (RUN-AGAIN = 'Y' OR 'y')
         GO TO 100-RANDGEN-EDIT-HOUSEKEEPING.
       ACCEPT PAUSE-FOR-A-SECOND.
       GOBACK.

Die meisten Antworten hier garantieren nicht, dass sie nicht zweimal dieselbe Nummer zurückgeben. Hier ist eine richtige Lösung:

int nrrand(void) {
  static int s = 1;
  static int start = -1;
  do {
    s = (s * 1103515245 + 12345) & 1023;
  } while (s >= 1001);
  if (start < 0) start = s;
  else if (s == start) abort();

  return s;
}

Ich bin nicht sicher, ob die Einschränkung gut spezifiziert ist. Man nimmt an, dass nach 1000 anderen Ausgaben ein Wert wiederholt werden darf, aber dass naiv 0 unmittelbar nach 0 folgen kann, solange beide am Ende und am Anfang von Sätzen von 1000 erscheinen. Umgekehrt ist es möglich, einen Abstand von zu halten 1000 andere Werte zwischen Wiederholungen erzwingen eine Situation, in der sich die Sequenz jedes Mal auf genau dieselbe Weise wiedergibt, da kein anderer Wert außerhalb dieses Grenzwerts aufgetreten ist.

Hier ist eine Methode, die immer mindestens 500 andere Werte garantiert, bevor ein Wert wiederholt werden kann:

int nrrand(void) {
  static int h[1001];
  static int n = -1;

  if (n < 0) {
    int s = 1;
    for (int i = 0; i < 1001; i++) {
      do {
        s = (s * 1103515245 + 12345) & 1023;
      } while (s >= 1001);
      /* If we used `i` rather than `s` then our early results would be poorly distributed. */
      h[i] = s;
    }
    n = 0;
  }

  int i = rand(500);
  if (i != 0) {
      i = (n + i) % 1001;
      int t = h[i];
      h[i] = h[n];
      h[n] = t;
  }
  i = h[n];
  n = (n + 1) % 1001;

  return i;
}

Wenn N größer als 1000 ist und Sie K Zufallsstichproben ziehen müssen, können Sie einen Satz verwenden, der die bisherigen Stichproben enthält. Für jede Ziehung verwenden Sie die Ablehnungsstichprobe , bei der es sich um eine "fast" O (1) -Operation handelt, sodass die Gesamtlaufzeit bei O (N) -Speicherung nahezu O (K) beträgt.

Dieser Algorithmus stößt auf Kollisionen, wenn K "nahe" N ist. Dies bedeutet, dass die Laufzeit viel schlechter als O (K) ist. Eine einfache Lösung besteht darin, die Logik umzukehren, sodass Sie für K> N / 2 alle noch nicht gezogenen Stichproben aufzeichnen. Bei jeder Ziehung wird eine Probe aus dem Ablehnungssatz entfernt.

Das andere offensichtliche Problem bei der Ablehnungsabtastung besteht darin, dass es sich um einen O (N) -Speicher handelt, was eine schlechte Nachricht ist, wenn N in Milliardenhöhe oder mehr liegt. Es gibt jedoch einen Algorithmus, der dieses Problem löst. Dieser Algorithmus wird nach seinem Erfinder Vitters Algorithmus genannt. Der Algorithmus wird beschrieben hier . Der Kern des Vitter-Algorithmus besteht darin, dass Sie nach jeder Ziehung einen zufälligen Sprung mit einer bestimmten Verteilung berechnen, die eine gleichmäßige Abtastung garantiert.

Fischer Yates

for i from n−1 downto 1 do
     j ← random integer such that 0 ≤ j ≤ i
     exchange a[j] and a[i]

Es ist tatsächlich O (n-1), da Sie nur einen Swap für die letzten beiden benötigen.
Dies ist C #

public static List<int> FisherYates(int n)
{
    List<int> list = new List<int>(Enumerable.Range(0, n));
    Random rand = new Random();
    int swap;
    int temp;
    for (int i = n - 1; i > 0; i--)
    {
        swap = rand.Next(i + 1);  //.net rand is not inclusive
        if(swap != i)  // it can stay in place - if you force a move it is not a uniform shuffle
        {
            temp = list[i];
            list[i] = list[swap];
            list[swap] = temp;
        }
    }
    return list;
}

Bitte sehen Sie meine Antwort unter https://stackoverflow.com/a/46807110/8794687

Es ist eine der einfachsten Algorithmen , die durchschnittliche Zeit , Komplexität haben O ( s log s ), s die Stichprobengröße bezeichnet. Es gibt dort auch einige Links zu Hash-Tabellen-Algorithmen, deren Komplexität angeblich O ( s ) ist.

Jemand hat "Zufallszahlen in Excel erstellen" gepostet. Ich benutze dieses Ideal. Erstellen Sie eine Struktur mit 2 Teilen, str.index und str.ran; Erstellen Sie für 10 Zufallszahlen ein Array von 10 Strukturen. Setzen Sie den str.index von 0 auf 9 und str.ran auf eine andere Zufallszahl.

for(i=0;i<10; ++i) {
      arr[i].index = i;
      arr[i].ran   = rand();
}

Sortieren Sie das Array nach den Werten in arr [i] .ran. Der str.index ist jetzt in zufälliger Reihenfolge. Unten ist c Code:

#include <stdio.h>
#include <stdlib.h>

struct RanStr { int index; int ran;};
struct RanStr arr[10];

int sort_function(const void *a, const void *b);

int main(int argc, char *argv[])
{
   int cnt, i;

   //seed(125);

   for(i=0;i<10; ++i)
   {
      arr[i].ran   = rand();
      arr[i].index = i;
      printf("arr[%d] Initial Order=%2d, random=%d\n", i, arr[i].index, arr[i].ran);
   }

   qsort( (void *)arr, 10, sizeof(arr[0]), sort_function);
   printf("\n===================\n");
   for(i=0;i<10; ++i)
   {
      printf("arr[%d] Random  Order=%2d, random=%d\n", i, arr[i].index, arr[i].ran);
   }

   return 0;
}

int sort_function(const void *a, const void *b)
{
   struct RanStr *a1, *b1;

   a1=(struct RanStr *) a;
   b1=(struct RanStr *) b;

   return( a1->ran - b1->ran );
}