webentwicklung-frage-antwort-db.com.de

Einmalige (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 das sucht nicht nach einer Suche nach O(N) vorheriger Werte TU es. Ist das möglich?

168
dicroce

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 Nummer an der Position r mit der Nummer an der Position max aus und geben Sie die Nummer 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 beginnen Sie erneut, ohne das Array neu initialisieren zu müssen.

Update: Obwohl ich diese Methode selbst beantragt hatte, als ich die Frage beantwortete, erkenne ich nach einiger Recherche, dass dies eine modifizierte Version von Fisher-Yates als Durstenfeld-Fisher-Yates ist oder Knuth-Fisher-Yates. Da die Beschreibung ein wenig schwierig zu befolgen ist, habe ich unten ein Beispiel gegeben (11 Elemente anstelle von 1001):

Das Array beginnt mit 11 Elementen, die mit Array [n] = n initialisiert wurden, wobei der Maximalwert bei 10 beginnt:

+--+--+--+--+--+--+--+--+--+--+--+
| 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 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 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.

231
Robert Gamble

Du kannst das:

  1. Erstellen Sie eine Liste, 0..1000.
  2. Mischen Sie die Liste. (Siehe Fisher-Yates shuffle für einen guten Weg, dies zu tun.)
  3. Geben Sie die Nummern in der Reihenfolge aus der gemischten Liste zurück.

Daher muss nicht jedes Mal nach alten Werten gesucht werden, sondern es wird immer noch O(N) für die erste Umstellung benötigt. Aber wie Nils in Kommentaren hervorhob, wird dies amortisiert O (1).

71

Verwenden Sie ein Maximum Linear Feedback Shift Register .

Es ist in ein paar Zeilen von C implementierbar und führt zur Laufzeit wenig mehr als ein paar Test-/Verzweigungen, ein kleines Addieren und ein bisschen Verschieben aus. Es ist nicht zufällig, aber die meisten Leute täuschen.

56
plinth

Sie könnten A Linear Congruential Generator verwenden. Wobei m (der Modulus) die nächste Primzahl größer als 1000 wäre. Wenn Sie eine Zahl außerhalb des Bereichs erhalten, erhalten Sie einfach die nächste. Die Sequenz wird nur wiederholt, wenn alle Elemente aufgetreten sind und Sie keine Tabelle verwenden müssen. Seien Sie sich jedoch der Nachteile dieses Generators bewusst (einschließlich mangelnder Zufälligkeit).

19
Paul de Vrieze

Sie können Format-Preserving Encryption 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 beliebiger Basis und Breite zu verwandeln. Z.B. Für das Beispiel in dieser Frage: Radix 10, Breite 3.

Blockverschlüsselungen haben normalerweise eine feste Blockgröße von z. 64 oder 128 Bit. Mit Format-Preserving Encryption können Sie jedoch eine Standard-Chiffre wie AES verwenden und mit einem Algorithmus, der immer noch kryptographisch robust ist, eine Chiffre mit geringerer Breite und beliebiger Basis und Breite erstellen.

Es ist garantiert, dass es niemals zu Kollisionen kommt (da kryptographische Algorithmen eine 1: 1-Zuordnung erstellen). Es ist auch reversibel (ein 2-Wege-Mapping), sodass Sie die resultierende Zahl übernehmen und zum Zählerwert zurückkehren können, mit dem Sie begonnen haben.

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

AES-FFX ist eine vorgeschlagene Standardmethode, um dies zu erreichen. Ich habe mit etwas grundlegendem Python-Code experimentiert, der auf der AES-FFX-Idee basiert, obwohl er nicht vollständig konform ist - siehe Python-Code hier . Es kann z. Verschlüsseln Sie einen Zähler mit einer 7-stelligen Dezimalzahl oder einer 16-Bit-Zahl. Hier ist ein Beispiel für Radix 10, Breite 3 (um eine Zahl zwischen 0 und 999 anzugeben), 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 Chiffrierschlüssel, um verschiedene nicht wiederholte Pseudozufallssequenzen zu erhalten. Jeder Verschlüsselungsschlüssel erzeugt eine andere, sich nicht wiederholende Pseudozufallsfolge.

15
Craig McQueen

Bei niedrigen Zahlen wie 0 ... 1000 ist das Erstellen einer Liste mit allen Zahlen und das Mischen unkompliziert. Wenn die Anzahl der zu ziehenden Zahlen jedoch sehr groß ist, gibt es eine andere elegante Methode: Sie können eine pseudozufällige Permutation mithilfe eines Schlüssels und einer kryptografischen Hash-Funktion erstellen. Siehe den folgenden C++ - ish-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 ist hash nur eine beliebige zufällige Pseudo-Zufallsfunktion, die eine Zeichenfolge einer möglicherweise großen vorzeichenlosen Ganzzahl zuordnet. Die Funktion randperm ist 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 index ändert, umkehrbar ist. Dies wird durch eine Feistel-Chiffre inspiriert.

7
sellibitze

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

http://openpatent.blogspot.co.il/201/04/04/xincrol-unique-and-randomnumber.html

Dies ist eine reine algorithmische Methode zum Generieren zufälliger, aber eindeutiger Zahlen ohne Arrays, Listen, Permutationen oder hohe CPU-Last.

In der neuesten Version können Sie auch den Zahlenbereich einstellen. Wenn Sie beispielsweise eindeutige Zufallszahlen im Bereich von 0-1073741821 wünschen.

Ich habe es praktisch für verwendet 

  • MP3-Player, der jeden Song nach dem Zufallsprinzip wiedergibt, jedoch nur einmal pro Album/Verzeichnis
  • Auflösungseffekt für pixelweise Videoframes (schnell und glatt)
  • Erstellen eines geheimen "Noise" -Nebelbildes für Signaturen und Marker (Steganographie)
  • Datenobjekt-IDs zur Serialisierung einer großen Anzahl von Java-Objekten über Datenbanken
  • Triple-Majority-Speicherbits
  • Adress- + Wert-Verschlüsselung (jedes Byte wird nicht nur verschlüsselt, sondern auch an einen neuen verschlüsselten Speicherort im Puffer verschoben). Das hat die Kryptoanalyse wirklich verrückt gemacht :-)
  • Klartext wie Crypt Textverschlüsselung für SMS, E-Mails usw.
  • Mein Texas Hold'em Poker-Rechner (THC)
  • Einige meiner Spiele für Simulationen, "Shuffling", Ranking 
  • mehr

Es ist offen und frei. Versuche es... 

6
Tod Samay

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

Sie brauchen 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 eingestellt), um eine Pseudo-Zufallszahl zu erzeugen. Wenn Sie keine Zahlen größer als 1000 haben können, verwenden Sie keine Bitmaske, die breiter als 9 Bit ist. (Mit anderen Worten, die Bitmaske ist eine ganze Zahl, die nicht über 511 liegt.)

Stellen Sie sicher, dass Sie den Zähler auf Null zurückstellen, wenn der Zähler 1000 durchläuft. Zu diesem Zeitpunkt können Sie - wenn Sie möchten - eine andere zufällige Bitmaske auswählen, um denselben Zahlensatz in einer anderen Reihenfolge zu erzeugen.

5
Max

Hier ist ein Code, den ich eingetippt habe, der die Logik der ersten Lösung verwendet. Ich weiß, dass dies "sprachunabhängig" ist, aber ich wollte es nur als Beispiel in C # vorstellen, 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]);
}
3
firedrawndagger

Diese Methode ergibt sich dann, wenn das Limit high 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 jedoch danach mischen.

3
salva

Sie könnten einen guten Pseudo-Zufallszahlengenerator mit 10 Bits verwenden und 1001 bis 1023 wegwerfen, wobei 0 bis 1000 verbleiben.

Von hier erhalten wir das Design für einen 10-Bit-PRNG.

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

  • verwenden Sie eine Galois LFSR, um schnellen Code zu erhalten

2
pro

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

 enter image description here

und es gibt nur drei Beschränkungen für die Werte a, c und m

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

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 funktionieren 

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

X = (1002 * X + 757) mod 1001
2
Max Abramovich
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 wiederholende Zufallszahlen sind nach Bedarf von O(n) Komplexität.
Hinweis: Random sollte statisch sein, wenn Threadsicherheit angewendet wird.

2
Erez Robinson

Nehmen wir an, Sie möchten die gemischten Listen immer und immer wieder durchgehen, ohne dass Sie bei jedem Neustart die O(n)-Verzögerung neu beginnen müssen.

  1. Erstellen Sie 2 Listen A und B mit 0 bis 1000 und 2n Speicherplatz.

  2. Die Shuffle-Liste A mit Fisher-Yates benötigt n Zeit.

  3. Machen Sie beim Zeichnen einer Nummer die Fisher-Yates-Zufallswiedergabe in der anderen Liste 1-Schritt.

  4. Wenn sich der Cursor am Ende der Liste 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
2
Khaled.K

Hier ist ein Beispiel-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 möchten.

   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.
1
Myron Denson

Andere Möglichkeit:

Sie können ein Array von Flags verwenden. Und nimm das nächste, wenn es schon gewählt ist.

Aber Achtung, nach 1000 Aufrufen wird die Funktion nie enden.

1
Toon Krijthe

Wenn N größer als 1000 ist und Sie K-Stichproben ziehen müssen, können Sie einen Satz verwenden, der die Stichproben enthält. Für jede Ziehung verwenden Sie Rejection Sampling , was eine Operation "fast" O(1) ist. Die Gesamtlaufzeit beträgt also nahezu O(K) mit O(N) Lagerung.

Dieser Algorithmus führt zu Kollisionen, wenn K "nahe" N ist. Dies bedeutet, dass die Laufzeit viel schlechter ist als O (K). Eine einfache Lösung besteht darin, die Logik umzukehren, so dass Sie für K> N/2 alle noch nicht gezogenen Proben aufzeichnen. Bei jeder Ziehung wird ein Muster aus dem Ablehnungssatz entfernt.

Das andere offensichtliche Problem bei der Ablehnungsabtastung ist, dass es sich um 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 Vitter-Algorithmus genannt. Der Algorithmus wird hier beschrieben. Der wichtigste Algorithmus von Vitter besteht darin, dass Sie nach jeder Ziehung einen Zufallssprung mit einer bestimmten Verteilung berechnen, die eine einheitliche Abtastung garantiert.

1

Die Frage Wie generieren Sie effizient eine Liste von K nicht wiederkehrenden ganzen Zahlen zwischen 0 und einer oberen Schranke N ist als Duplikat verknüpft - und wenn Sie etwas wollen, das O(1) für jede generierte Zufallszahl ist Nummer (ohne O(n) Startkosten))) Es gibt einen einfachen Tweak der akzeptierten Antwort.

Erstellen Sie eine leere ungeordnete Karte (eine leere geordnete Karte nimmt O (log k) pro Element an) von Ganzzahl zu Ganzzahl - anstelle eines initialisierten Arrays . 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 die beiden 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. Swap-Elemente r und max 
  4. Element max zurückgeben und max um 1 dekrementieren (wenn max negativ wird Sie sind 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 exakt dieselben Zahlen aus demselben PRNG generiert.

1
Hans Olsson

Die meisten Antworten hier garantieren nicht, dass sie dieselbe Nummer nicht zweimal 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 mir nicht sicher, ob die Einschränkung genau angegeben ist. Man geht davon aus, dass sich nach 1000 anderen Ausgängen ein Wert wiederholen darf, der aber naiv erlaubt, 0 unmittelbar nach 0 zu folgen, solange beide am Ende und am Anfang von Mengen von 1000 erscheinen 1000 andere Werte zwischen Wiederholungen erzwingen eine Situation, in der sich die Sequenz jedes Mal auf dieselbe Weise wiederholt, weil es keinen anderen Wert gibt, der 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;
}
1
sh1

Fisher 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 für die letzten beiden nur einen Swap 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;
}
0
paparazzo

Siehe meine Antwort unter https://stackoverflow.com/a/46807110/8794687

Dies ist einer der einfachsten Algorithmen mit durchschnittlicher Zeitkomplexität O (s log s), wobei s die Stichprobengröße bezeichnet. Es gibt auch einige Links zu Hash-Tabellen-Algorithmen, deren Komplexität O (s) sein soll.

0
Pavel Ruzankin