Nomor acak unik (tidak berulang) di O (1)?

Saya ingin menghasilkan angka acak unik antara 0 dan 1000 yang tidak pernah diulang (yaitu 6 tidak muncul dua kali), tetapi itu tidak menggunakan sesuatu seperti pencarian O (N) dari nilai sebelumnya untuk melakukannya. Apakah ini mungkin?

Inisialisasi array 1001 integer dengan nilai 0-1000 dan atur variabel, maks, ke indeks maks saat ini dari array (dimulai dengan 1000). Pilih angka acak, r, antara 0 dan maks, tukar angka di posisi r dengan angka di posisi max dan kembalikan angka sekarang di posisi maks. Mengurangi maks. 1 dan melanjutkan. Ketika max adalah 0, atur max kembali ke ukuran array - 1 dan mulai lagi tanpa perlu menginisialisasi ulang array.

Pembaruan: Meskipun saya menemukan metode ini sendiri ketika saya menjawab pertanyaan, setelah beberapa penelitian saya menyadari ini adalah versi modifikasi dari Fisher-Yates yang dikenal sebagai Durstenfeld-Fisher-Yates atau Knuth-Fisher-Yates. Karena uraiannya mungkin agak sulit untuk diikuti, saya telah memberikan contoh di bawah ini (menggunakan 11 elemen, bukan 1001):

Array dimulai dengan 11 elemen yang diinisialisasi ke array [n] = n, maks dimulai pada 10:

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

Pada setiap iterasi, angka acak r dipilih antara 0 dan maks, array [r] dan array [maks] ditukar, array baru [maks] dikembalikan, dan maks dikurangi:

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

...

Setelah 11 iterasi, semua angka dalam array telah dipilih, maks == 0, dan elemen array diacak:

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

Pada titik ini, maks dapat diatur ulang ke 10 dan proses dapat dilanjutkan.

Kamu bisa melakukan ini:

1. Buat daftar, 0..1000.
2. Kocok daftar. (Lihat Fisher-Yates shuffle untuk cara yang baik untuk melakukan ini.)
3. Kembalikan angka secara berurutan dari daftar acak.

Jadi ini tidak memerlukan pencarian nilai-nilai lama setiap kali, tetapi masih membutuhkan O (N) untuk pengocokan awal. Tetapi seperti yang ditunjukkan Nils dalam komentar, ini diamortisasi O (1).

Gunakan Register Pergeseran Umpan Balik Linier Maksimal .

Ini dapat diimplementasikan dalam beberapa baris C dan pada saat runtime melakukan sedikit lebih dari beberapa tes / cabang, sedikit tambahan dan sedikit bergeser. Ini tidak acak, tetapi menipu kebanyakan orang.

Anda bisa menggunakan A Linear Congruential Generator . Di mana m(modulus) akan menjadi bilangan prima terdekat yang lebih besar dari 1000. Saat Anda mendapatkan angka di luar rentang, dapatkan yang berikutnya. Urutan hanya akan mengulangi setelah semua elemen terjadi, dan Anda tidak perlu menggunakan tabel. Berhati-hatilah dengan kelemahan generator ini (termasuk kurangnya keacakan).

Anda bisa menggunakan Enkripsi Format-Pelestarian untuk mengenkripsi penghitung. Penghitung Anda hanya beranjak dari 0 ke atas, dan enkripsi menggunakan kunci pilihan Anda untuk mengubahnya menjadi nilai acak dari radix dan lebar apa pun yang Anda inginkan. Misalnya untuk contoh dalam pertanyaan ini: radix 10, lebar 3.

Cipher blok biasanya memiliki ukuran blok tetap misalnya 64 atau 128 bit. Tapi Enkripsi Format-Preserving memungkinkan Anda untuk mengambil cipher standar seperti AES dan membuat cipher-lebar yang lebih kecil, dari apa pun radix dan lebar yang Anda inginkan, dengan algoritma yang masih kuat secara kriptografi.

Dijamin tidak akan ada tabrakan (karena algoritma kriptografi membuat pemetaan 1: 1). Ini juga reversibel (pemetaan 2 arah), sehingga Anda dapat mengambil angka yang dihasilkan dan kembali ke nilai penghitung yang Anda mulai.

Teknik ini tidak memerlukan memori untuk menyimpan array shuffled dll, yang dapat menjadi keuntungan pada sistem dengan memori terbatas.

AES-FFX adalah salah satu metode standar yang diusulkan untuk mencapai ini. Saya telah bereksperimen dengan beberapa kode Python dasar yang didasarkan pada ide AES-FFX, meskipun tidak sepenuhnya sesuai - lihat kode Python di sini . Misalnya, mengenkripsi penghitung ke angka desimal 7 digit yang terlihat acak, atau angka 16-bit. Berikut adalah contoh radix 10, lebar 3 (untuk memberikan angka antara 0 dan 999 inklusif) seperti yang dinyatakan pertanyaan:

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

Untuk mendapatkan urutan pseudo-acak non-berulang yang berbeda, ubah kunci enkripsi. Setiap kunci enkripsi menghasilkan urutan pseudo-acak non-berulang yang berbeda.

Untuk angka rendah seperti 0 ... 1000, buat daftar yang berisi semua angka dan mengocoknya lurus ke depan. Tetapi jika himpunan angka untuk menarik sangat besar ada cara lain yang elegan: Anda dapat membangun permutasi pseudorandom menggunakan kunci dan fungsi hash kriptografi. Lihat C ++ - ish contoh kode pseudo berikut:

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

Di sini, hashhanya beberapa fungsi acak semu yang memetakan string karakter ke integer unsigned yang mungkin besar. Fungsi randpermini adalah permutasi dari semua angka dalam 0 ... pow (2, bits) -1 dengan asumsi kunci tetap. Ini mengikuti dari konstruksi karena setiap langkah yang mengubah variabel indexreversibel. Ini terinspirasi oleh cipher Feistel .

Anda dapat menggunakan algoritma Xincrol saya yang dijelaskan di sini:

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

Ini adalah metode algoritmik murni untuk menghasilkan angka acak tetapi unik tanpa array, daftar, permutasi, atau beban CPU yang berat.

Versi terbaru juga memungkinkan untuk mengatur kisaran angka, Misalnya, jika saya ingin angka acak unik dalam kisaran 0-1073741821.

Saya praktis menggunakannya untuk

• MP3 player yang memainkan setiap lagu secara acak, tetapi hanya sekali per album / direktori
• Efek pelarutan bingkai video yang bijak piksel (cepat dan halus)
• Menciptakan kabut "noise" rahasia di atas gambar untuk tanda tangan dan spidol (steganografi)
• ID Objek Data untuk serialisasi sejumlah besar objek Java melalui Database
• Perlindungan bit memori Triple Majority
• Enkripsi alamat + nilai (setiap byte tidak hanya dienkripsi saja, tetapi juga dipindahkan ke lokasi terenkripsi baru di buffer). Ini benar-benar membuat rekan cryptanalysis marah pada saya :-)
• Enkripsi Teks Biasa ke Biasa Seperti Crypt Text untuk SMS, email, dll.
• Kalkulator Poker Texas Hold`em Texas (THC)
• Beberapa game saya untuk simulasi, "pengacakan", peringkat
• lebih

Ini terbuka, gratis. Cobalah...

Anda bahkan tidak memerlukan array untuk menyelesaikannya.

Anda membutuhkan bitmask dan counter.

Inisialisasi penghitung ke nol dan tambahkan pada panggilan yang berurutan. XOR penghitung dengan bitmask (dipilih secara acak saat startup, atau diperbaiki) untuk menghasilkan nomor psuedorandom. Jika Anda tidak dapat memiliki angka yang melebihi 1000, jangan gunakan bitmask yang lebih lebar dari 9 bit. (Dengan kata lain, bitmask adalah bilangan bulat tidak di atas 511.)

Pastikan bahwa ketika penghitung melewati 1000, Anda meresetnya ke nol. Pada saat ini Anda dapat memilih bitmask acak lain - jika diinginkan - untuk menghasilkan rangkaian angka yang sama dalam urutan yang berbeda.

Saya pikir generator kongruensial Linear akan menjadi solusi paling sederhana.

dan hanya ada 3 pembatasan pada suatu , c dan m nilai-nilai

1. m dan c relatif prima,
2. a-1 dapat dibagi oleh semua faktor utama m
3. a-1 habis dibagi 4 jika m habis dibagi 4

PS metode telah disebutkan tetapi posting memiliki asumsi yang salah tentang nilai konstan. Konstanta di bawah ini akan berfungsi dengan baik untuk kasus Anda

Dalam kasus Anda Anda dapat menggunakan a = 1002, c = 757,m = 1001

X = (1002 * X + 757) mod 1001

Berikut ini beberapa kode yang saya ketikkan yang menggunakan logika solusi pertama. Saya tahu ini "agnostik bahasa" tetapi hanya ingin menyajikan ini sebagai contoh dalam C # jika ada yang mencari solusi praktis cepat.

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

Metode ini menghasilkan tepat ketika batasnya tinggi dan Anda hanya ingin menghasilkan beberapa angka acak.

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

Perhatikan bahwa angka-angka tersebut dihasilkan dalam urutan menaik, tetapi Anda dapat mengocoknya kemudian.

Anda bisa menggunakan generator angka pseudo-acak yang baik dengan 10 bit dan membuang 1001 ke 1023 meninggalkan 0 hingga 1000.

Dari sini kita mendapatkan desain untuk PRNG 10 bit ..

• 10 bit, umpan balik polinomial x ^ 10 + x ^ 7 + 1 (periode 1023)

• gunakan Galois LFSR untuk mendapatkan kode cepat

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 Angka acak yang tidak berulang akan menjadi O (n) rumit, seperti yang diperlukan.
Catatan: Acak harus statis dengan keamanan ulir diterapkan.

Katakanlah Anda ingin membahas daftar yang diacak berulang-ulang, tanpa O(n)penundaan setiap kali Anda memulai untuk mengacaknya lagi, dalam hal ini kita dapat melakukan ini:

1. Buat 2 daftar A dan B, dengan 0 hingga 1000, membutuhkan 2nruang.

2. Daftar acak A menggunakan Fisher-Yates, membutuhkan nwaktu.

3. Saat menggambar nomor, lakukan shuffle Fisher-Yates 1-langkah pada daftar lainnya.

4. Ketika kursor berada di ujung daftar, beralih ke daftar lainnya.

Praproses

cursor = 0

selector = A
other    = B

shuffle(A)

Seri

temp = selector[cursor]

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

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

return temp

Pertanyaannya Bagaimana Anda secara efisien menghasilkan daftar bilangan bulat non-berulang K antara 0 dan batas atas N dihubungkan sebagai duplikat - dan jika Anda menginginkan sesuatu yang O (1) per angka acak yang dihasilkan (tanpa O (n) biaya awal)) ada perubahan sederhana dari jawaban yang diterima.

Buat peta kosong yang tidak berurutan (peta yang kosong akan mengambil O (log k) per elemen) dari integer ke integer - alih-alih menggunakan array yang diinisialisasi. Tetapkan maks ke 1000 jika itu adalah maksimum,

1. Pilih angka acak, r, antara 0 dan maks.
2. Pastikan bahwa kedua elemen peta r dan maks ada di peta yang tidak berurutan. Jika tidak ada, buat dengan nilai yang sama dengan indeks mereka.
3. Tukar elemen r dan maks
4. Kembalikan elemen maks dan perkecil maks. 1 (jika maks negatif Anda selesai).
5. Kembali ke langkah 1.

Satu-satunya perbedaan dibandingkan dengan menggunakan array diinisialisasi adalah bahwa inisialisasi elemen ditunda / dilewati - tetapi akan menghasilkan angka yang sama persis dari PRNG yang sama.

Kemungkinan lain:

Anda dapat menggunakan berbagai flag. Dan ambil yang berikutnya ketika sudah dipilih.

Namun, waspadalah setelah 1000 panggilan, fungsi ini tidak akan pernah berakhir sehingga Anda harus membuat perlindungan.

Berikut ini beberapa contoh kode COBOL yang dapat Anda mainkan.
Saya dapat mengirimi Anda file RANDGEN.exe sehingga Anda dapat bermain dengannya untuk melihat apakah ia menginginkannya.

   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.

Sebagian besar jawaban di sini gagal menjamin bahwa mereka tidak akan mengembalikan nomor yang sama dua kali. Inilah solusi yang benar:

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

Saya tidak yakin batasannya ditentukan dengan baik. Satu mengasumsikan bahwa setelah 1000 output lainnya nilai diizinkan untuk diulang, tetapi bahwa secara naif memungkinkan 0 untuk mengikuti segera setelah 0 asalkan keduanya muncul di akhir dan mulai dari set 1000. Sebaliknya, sementara itu dimungkinkan untuk menjaga jarak dari 1000 nilai lain di antara pengulangan, melakukan hal itu memaksa situasi di mana urutan memutar ulang dengan cara yang persis sama setiap kali karena tidak ada nilai lain yang terjadi di luar batas itu.

Berikut adalah metode yang selalu menjamin setidaknya 500 nilai lain sebelum nilai dapat diulang:

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

Ketika N lebih besar dari 1000 dan Anda perlu menggambar sampel acak K Anda bisa menggunakan satu set yang berisi sampel sejauh ini. Untuk setiap undian, Anda menggunakan sampel penolakan , yang akan menjadi operasi "hampir" O (1), sehingga total waktu berjalan hampir O (K) dengan penyimpanan O (N).

Algoritma ini mengalami tabrakan ketika K "dekat" N. Ini berarti waktu berjalan akan jauh lebih buruk daripada O (K). Perbaikan sederhana adalah membalikkan logika sehingga, untuk K> N / 2, Anda menyimpan catatan semua sampel yang belum diambil. Setiap undian menghapus sampel dari set penolakan.

Masalah lain yang jelas dengan sampel penolakan adalah penyimpanan O (N), yang merupakan berita buruk jika N ada dalam miliaran atau lebih. Namun, ada algoritma yang memecahkan masalah itu. Algoritma ini disebut algoritma Vitter setelah penemunya. Algoritma dijelaskan di sini . Inti dari algoritma Vitter adalah bahwa setelah setiap pengundian, Anda menghitung lompatan acak menggunakan distribusi tertentu yang menjamin pengambilan sampel yang seragam.

Fisher Yates

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

Ini sebenarnya O (n-1) karena Anda hanya perlu satu swap untuk dua yang terakhir.
Ini adalah 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;
}

Silakan lihat jawaban saya di https://stackoverflow.com/a/46807110/8794687

Ini adalah salah satu algoritma paling sederhana yang memiliki rata-rata waktu kompleksitas O ( s log s ), s yang menunjukkan ukuran sampel. Ada juga beberapa tautan di sana ke algoritma tabel hash yang kompleksitasnya diklaim sebagai O ( s ).

Seseorang memposting "membuat angka acak di excel". Saya menggunakan ideal ini. Buat struktur dengan 2 bagian, str.index dan str.ran; Untuk 10 angka acak, buat array 10 struktur. Atur str.index dari 0 hingga 9 dan str.ran ke nomor acak berbeda.

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

Urutkan array pada nilai-nilai di arr [i] .ran. Str.index sekarang dalam urutan acak. Di bawah ini adalah kode 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 );
}