Unikalne (niepowtarzalne) liczby losowe w O (1)?

Chciałbym wygenerować unikalne liczby losowe z zakresu od 0 do 1000, które nigdy się nie powtarzają (tj. 6 nie pojawia się dwukrotnie), ale to nie ucieka się do czegoś w rodzaju wyszukiwania O (N) poprzednich wartości, aby to zrobić. czy to możliwe?

Zainicjuj tablicę 1001 liczb całkowitych o wartościach od 0 do 1000 i ustaw zmienną max na bieżący maksymalny indeks tablicy (zaczynając od 1000). Wybierz losową liczbę, r, od 0 do max, zamień liczbę na pozycji r liczbą na pozycji max i zwróć liczbę na pozycji max. Zmniejsz maksymalnie o 1 i kontynuuj. Gdy max wynosi 0, ustaw max z powrotem na rozmiar tablicy - 1 i zacznij od nowa bez potrzeby ponownej inicjalizacji tablicy.

Aktualizacja: Chociaż wymyśliłem tę metodę samodzielnie, kiedy odpowiedziałem na pytanie, po kilku badaniach zdaję sobie sprawę, że jest to zmodyfikowana wersja Fisher-Yatesa znana jako Durstenfeld-Fisher-Yates lub Knuth-Fisher-Yates. Ponieważ opis może być trochę trudny do zrozumienia, poniżej podałem przykład (używając 11 elementów zamiast 1001):

Tablica zaczyna się od 11 elementów zainicjowanych w tablicy [n] = n, max zaczyna się od 10:

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

Przy każdej iteracji wybierana jest losowa liczba r z zakresu od 0 do max, tablica [r] i tablica [max] są zamieniane, zwracana jest nowa tablica [max], a wartość max jest zmniejszana:

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

...

Po 11 iteracjach wszystkie liczby w tablicy zostały wybrane, max == 0, a elementy tablicy są tasowane:

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

W tym momencie max można zresetować do 10 i proces może być kontynuowany.

Możesz to zrobić:

1. Utwórz listę, 0..1000.
2. Potasuj listę. (Zobacz tasowanie Fisher-Yates, aby dowiedzieć się, jak to zrobić).
3. Zwraca liczby w kolejności z potasowanej listy.

Więc to nie wymaga wyszukiwania starych wartości za każdym razem, ale nadal wymaga O (N) do początkowego tasowania. Ale jak zauważył Nils w komentarzach, jest to amortyzowane O (1).

Użyj rejestru przesunięcia maksymalnego liniowego sprzężenia zwrotnego .

Można go zaimplementować w kilku wierszach C, a w czasie wykonywania robi niewiele więcej niż kilka testów / gałęzi, trochę dodawania i nieco przesunięcia. To nie jest przypadkowe, ale większość ludzi oszukuje.

Możesz użyć liniowego generatora kongruencji . Gdzie m(moduł) byłby najbliższą liczbą pierwszą większą niż 1000. Kiedy otrzymasz liczbę spoza zakresu, po prostu uzyskaj następną. Sekwencja zostanie powtórzona dopiero po wystąpieniu wszystkich elementów i nie musisz używać tabeli. Należy jednak pamiętać o wadach tego generatora (w tym braku losowości).

Możesz użyć szyfrowania zachowującego format, aby zaszyfrować licznik. Twój licznik po prostu przechodzi od 0 w górę, a szyfrowanie używa wybranego klucza, aby przekształcić go w pozornie losową wartość o dowolnej podstawie i szerokości. Np. Na przykład w tym pytaniu: podstawa 10, szerokość 3.

Szyfry blokowe mają zwykle stały rozmiar bloku, np. 64 lub 128 bitów. Ale szyfrowanie z zachowaniem formatu pozwala ci wziąć standardowy szyfr, taki jak AES, i utworzyć szyfr o mniejszej szerokości, o dowolnej podstawie i szerokości, z algorytmem, który jest nadal niezawodny kryptograficznie.

Gwarantuje to, że nigdy nie wystąpią kolizje (ponieważ algorytmy kryptograficzne tworzą mapowanie 1: 1). Jest również odwracalne (mapowanie dwukierunkowe), więc możesz wziąć wynikową liczbę i wrócić do wartości licznika, od której zacząłeś.

Ta technika nie wymaga pamięci do przechowywania losowej tablicy itp., Co może być zaletą w systemach z ograniczoną pamięcią.

AES-FFX to jedna z proponowanych standardowych metod osiągnięcia tego celu. Eksperymentowałem z podstawowym kodem Pythona, który jest oparty na idei AES-FFX, chociaż nie jest w pełni zgodny - zobacz kod Pythona tutaj . Może np. Zaszyfrować licznik do losowo wyglądającej 7-cyfrowej liczby dziesiętnej lub 16-bitowej. Oto przykład podstawy 10, szerokość 3 (aby podać liczbę od 0 do 999 włącznie) zgodnie z pytaniem:

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

Aby uzyskać różne niepowtarzalne sekwencje pseudolosowe, zmień klucz szyfrowania. Każdy klucz szyfrowania tworzy inną niepowtarzalną pseudolosową sekwencję.

W przypadku niskich liczb, takich jak 0 ... 1000, tworzenie listy zawierającej wszystkie liczby i tasowanie jej jest proste. Ale jeśli zbiór liczb do losowania jest bardzo duży, istnieje inny elegancki sposób: możesz zbudować permutację pseudolosową za pomocą klucza i kryptograficznej funkcji skrótu. Zobacz poniższy przykładowy pseudokod w języku C ++:

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;
}

Oto hashtylko dowolna funkcja pseudolosowa, która odwzorowuje ciąg znaków na prawdopodobnie dużą liczbę całkowitą bez znaku. Funkcja randpermjest permutacją wszystkich liczb w zakresie 0 ... pow (2, bity) -1 przy założeniu stałego klucza. Wynika to z konstrukcji, ponieważ każdy krok zmieniający zmienną indexjest odwracalny. Jest to inspirowane szyfrem Feistela .

Możesz użyć mojego algorytmu Xincrol opisanego tutaj:

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

Jest to czysto algorytmiczna metoda generowania losowych, ale unikalnych liczb bez tablic, list, permutacji lub dużego obciążenia procesora.

Najnowsza wersja pozwala również ustawić zakres liczb, na przykład, jeśli chcę unikalnych liczb losowych z zakresu 0-1073741821.

Praktycznie to wykorzystałem

• Odtwarzacz MP3, który odtwarza każdą piosenkę losowo, ale tylko raz na album / katalog
• Efekt rozpuszczania klatek wideo w pikselach (szybki i płynny)
• Tworzenie tajnej mgły „szumu” nad obrazem dla podpisów i markerów (steganografia)
• Identyfikatory obiektów danych do serializacji ogromnej liczby obiektów Java za pośrednictwem baz danych
• Ochrona trzech bitów pamięci większości
• Szyfrowanie adresu + wartości (każdy bajt jest nie tylko szyfrowany, ale także przenoszony do nowej zaszyfrowanej lokalizacji w buforze). To naprawdę rozwścieczyło koleżanki z kryptoanalizy :-)
• Szyfrowanie zwykłego tekstu na zwykły tekst szyfrowany dla wiadomości SMS, e-maili itp.
• Mój kalkulator pokerowy Texas Hold`em (THC)
• Kilka moich gier do symulacji, "tasowania", rankingów
• więcej

Jest otwarte, bezpłatne. Spróbuj...

Nie potrzebujesz nawet tablicy, aby rozwiązać ten problem.

Potrzebujesz maski bitowej i licznika.

Zainicjuj licznik na zero i zwiększaj go przy kolejnych wywołaniach. XOR licznik z maską bitową (wybraną losowo podczas uruchamiania lub ustaloną), aby wygenerować liczbę psuedorandom. Jeśli nie możesz mieć liczb przekraczających 1000, nie używaj maski bitowej szerszej niż 9 bitów. (Innymi słowy, maska ​​bitowa jest liczbą całkowitą nie większą niż 511).

Upewnij się, że gdy licznik przekroczy 1000, zresetujesz go do zera. W tym momencie możesz wybrać inną losową maskę bitową - jeśli chcesz - aby wygenerować ten sam zestaw liczb w innej kolejności.

Myślę, że liniowy generator kongruencji byłby najprostszym rozwiązaniem.

i są tylko trzy ograniczenia A , C i m wartościami

1. m i c są liczbami względnie pierwszymi
2. a-1 jest podzielna przez wszystkie czynniki pierwsze m
3. a-1 jest podzielne przez 4, jeśli m jest podzielne przez 4

PS o metodzie już wspomniano, ale post zawiera błędne założenia co do stałych wartości. Poniższe stałe powinny działać dobrze w Twoim przypadku

W twoim przypadku można użyć a = 1002, c = 757,m = 1001

X = (1002 * X + 757) mod 1001

Oto kod, który napisałem, który wykorzystuje logikę pierwszego rozwiązania. Wiem, że jest to „język agnostyk”, ale chciałem tylko przedstawić to jako przykład w C # na wypadek, gdyby ktoś szukał szybkiego praktycznego rozwiązania.

// 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]);
}

Ta metoda jest odpowiednia, gdy limit jest wysoki i chcesz wygenerować tylko kilka liczb losowych.

#!/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";
}

Zwróć uwagę, że liczby są generowane w kolejności rosnącej, ale możesz później tasować.

Możesz użyć dobrego generatora liczb pseudolosowych z 10 bitami i odrzucić od 1001 do 1023, pozostawiając od 0 do 1000.

Od tutaj mamy projekt dla 10-bitowego PRNG ..

• 10 bitów, wielomian sprzężenia zwrotnego x ^ 10 + x ^ 7 + 1 (okres 1023)

• użyj Galois LFSR, aby uzyskać szybki kod

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 Niepowtarzające się liczby losowe będą miały złożoność O (n), zgodnie z wymaganiami.
Uwaga: losowość powinna być statyczna z zastosowanym zabezpieczeniem nici.

Powiedzmy, że chcesz przeglądać potasowane listy w kółko, bez O(n)opóźnienia za każdym razem, gdy zaczynasz od początku, aby ponownie tasować, w takim przypadku możemy zrobić to:

1. Utworzenie 2 list A i B, od 0 do 1000, zajmuje 2nmiejsce.

2. Przetasuj listę A przy użyciu Fisher-Yatesa, wymaga nczasu.

3. Rysując liczbę, wykonaj jednoetapowe tasowanie Fishera-Yatesa na drugiej liście.

4. Gdy kursor znajduje się na końcu listy, przełącz się na inną listę.

Przetwarzaj wstępnie

cursor = 0

selector = A
other    = B

shuffle(A)

Remis

temp = selector[cursor]

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

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

return temp

Pytanie Jak skutecznie wygenerować listę K nie powtarzających się liczb całkowitych od 0 do górnej granicy N jest połączone jako duplikat - a jeśli chcesz coś, co jest O (1) na wygenerowaną liczbę losową (bez O (n)) koszt uruchomienia)) istnieje prosta modyfikacja zaakceptowanej odpowiedzi.

Utwórz pustą mapę nieuporządkowaną (pusta mapa uporządkowana pobierze O (log k) na element) od liczby całkowitej do liczby całkowitej - zamiast używać zainicjowanej tablicy. Ustaw max na 1000, jeśli to jest maksimum,

1. Wybierz losową liczbę, r, od 0 do maks.
2. Upewnij się, że na nieuporządkowanej mapie istnieją oba elementy mapy r i max. Jeśli nie istnieją, utwórz je z wartością równą ich indeksowi.
3. Zamień elementy r i max
4. Zwróć max elementu i dekrementuj max o 1 (jeśli max jest ujemne, koniec).
5. Wróć do kroku 1.

Jedyną różnicą w porównaniu z użyciem zainicjalizowanej tablicy jest to, że inicjalizacja elementów jest odkładana / pomijana - ale wygeneruje dokładnie te same liczby z tego samego PRNG.

Inna możliwość:

Możesz użyć tablicy flag. I weź następny, gdy jest już wybrany.

Ale uważaj po 1000 wywołań, funkcja nigdy się nie skończy, więc musisz zrobić zabezpieczenie.

Oto przykładowy kod w języku COBOL, z którym możesz się pobawić.
Mogę wysłać Ci plik RANDGEN.exe, żebyś mógł się nim bawić i zobaczyć, czy chce, żebyś tego chciał.

   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.

Większość odpowiedzi nie gwarantuje, że nie zwrócą dwa razy tego samego numeru. Oto poprawne rozwiązanie:

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;
}

Nie jestem pewien, czy ograniczenie jest dobrze określone. Zakłada się, że po 1000 innych danych wyjściowych wartość może się powtórzyć, ale to naiwnie pozwala 0 następować natychmiast po zera, o ile oba pojawiają się na końcu i na początku serii 1000. I odwrotnie, podczas gdy można zachować odległość 1000 innych wartości między powtórzeniami, wymusza to sytuację, w której sekwencja powtarza się dokładnie w ten sam sposób za każdym razem, ponieważ żadna inna wartość nie wystąpiła poza tym limitem.

Oto metoda, która zawsze gwarantuje co najmniej 500 innych wartości, zanim wartość będzie mogła zostać powtórzona:

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;
}

Gdy N jest większe niż 1000 i musisz narysować K losowych próbek, możesz użyć zestawu, który zawiera próbki do tej pory. Dla każdego losowania używasz próbkowania odrzucania , które będzie operacją "prawie" O (1), więc całkowity czas pracy jest prawie O (K) z pamięcią O (N).

Algorytm ten napotyka na kolizje, gdy K jest „blisko” N. Oznacza to, że czas pracy będzie dużo gorszy niż O (K). Prostym rozwiązaniem jest odwrócenie logiki, tak aby dla K> N / 2 zachować zapis wszystkich próbek, które nie zostały jeszcze narysowane. Każde losowanie usuwa próbkę z zestawu odrzucania.

Innym oczywistym problemem związanym z próbkowaniem odrzucania jest to, że jest to pamięć O (N), co jest złą wiadomością, jeśli N jest w miliardach lub więcej. Istnieje jednak algorytm, który rozwiązuje ten problem. Algorytm ten nazywa się algorytmem Vittera od nazwiska jego wynalazcy. Algorytm został opisany tutaj . Istota algorytmu Vittera polega na tym, że po każdym losowaniu obliczasz losowe pominięcie przy użyciu określonego rozkładu, który gwarantuje jednolite próbkowanie.

Fisher Yates

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

W rzeczywistości jest to O (n-1) ponieważ potrzebujesz tylko jednej zamiany na ostatnie dwa
To jest 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;
}

Zobacz moją odpowiedź na https://stackoverflow.com/a/46807110/8794687

Jest to jedna z najprostszych algorytmów, które mają średni czas złożoność O ( y log s ) y oznaczającą wielkość próbki. Znajdują się tam również linki do algorytmów tablicy skrótów, których złożoność jest określana jako O ( s ).

Ktoś napisał „tworzenie liczb losowych w programie Excel”. Używam tego ideału. Utwórz strukturę z 2 części, str.index i str.ran; Dla 10 liczb losowych utwórz tablicę 10 struktur. Ustaw indeks str. Od 0 do 9 i str .ran na inną liczbę losową.

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

Sortuj tablicę według wartości w arr [i] .ran. Indeks str. Ma teraz losową kolejność. Poniżej znajduje się kod c:

#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 );
}