Algoritma yang paling efisien untuk mencetak 1-100 menggunakan generator angka acak yang diberikan

Kami diberi generator bilangan acak RandNum50yang menghasilkan bilangan bulat acak seragam di kisaran 1-50. Kami hanya dapat menggunakan generator angka acak ini untuk menghasilkan dan mencetak semua bilangan bulat dari 1 hingga 100 dalam urutan acak. Setiap angka harus tepat satu kali, dan probabilitas setiap angka yang terjadi di tempat mana pun harus sama.

Apa algoritma yang paling efisien untuk ini?

Saya pikir (jadi bisa salah :-) dari solusi yang menggunakan shuffle Fisher-Yates . Untuk menjaga distribusi yang seragam dengan pendekatan yang baik (lihat bagian EDIT di bawah) di setiap iterasi Anda dapat menggunakan trik ini untuk menghasilkan nilai antara 0 dan k - 1 :$O(N^2)$krand$0$$k-1$

 // return a random number in [0..k-1] with uniform distribution
 // using a uniform random generator in [1..50]
 funtion krand(k) {    
   sum = 0
   for i = 1 to k do sum = sum + RandNum50() - 1
   krand = sum mod k
 }

Algoritma Fisher-Yates menjadi:

arr : array[0..99]
for i = 0  to 99 do arr[i] = i+1; // store 1..100 in the array
for i = 99 downto 1 {
  r = krand(i+1)  // random value in [0..i]
  exchange the values of arr[i] and arr[r]
}
for i = 0 to 99 do print arr[i]

EDIT:

krand$m = \lceil \log_2(k) \rceil$$r$$k$

function trulyrand(k) {
    if (k <= 1) return 0
    while (true) { // ... if you're really unlucky ...
      m = ceil(log_2 (k) ) // calculate m such that k < 2^m
      r = 0  // will hold the random value
      while (m >= 0) {  // ... will add m bits        
        if ( rand50() > 25 ) then b = 1 else b = 0   // random bit
        r = r * 2 + b  // shift and add the random bit
        m = m - 1
      }      
      if (r < k) then return r  // we have 0<=r<2^m ; accept it, if r < k
    }
}

Karena orang lain telah memberikan solusi perkiraan dan solusi yang melibatkan pengambilan jumlah penyimpangan yang tidak pasti, bagaimana dengan bukti bahwa tidak ada algoritma yang dijamin hanya membutuhkan jumlah RandNum50()panggilan yang terbatas ?

$\frac{1}{100!}$

$k$RandNum50$k$$k$RandNum50$k$$k$RandNum50$(r_1, r_2, \ldots, r_k)$$\displaystyle\frac{1}{50^k}$$\displaystyle\frac{c}{50^k}$$c$$\displaystyle\frac{1}{100!}$$100!$$50^k$$k$$100!$$50^k$

$n\log n + O(1)$

if ( rand50() > 25 ) then b = 1 else b = 0   // random bit

$1$$n!$$1$$2$$3$$n$

Jika Anda tidak tahu cara membuat seragam, seperti yang disarankan dalam posting itu, dari bit acak, Anda juga bisa menghasilkan perkiraan seragam secara langsung, dengan cara ini (yang setara dengan "reallyrand" Vor, tetapi lebih cepat):

P = (RandNum50()-1) + (RandNum50()-1)*50^1 + (RandNum50()-1)*50^2 + ...

$P$$50$$P$$Q=P\mod n$$n=100!$$P>n$

Saya belum melakukan analisis untuk mengkonfirmasi seberapa seragam (atau tidak) ini akan, dan itu bisa disesuaikan menjadi shuffle yang benar, tetapi bisakah Anda memilih, dari susunan awal dari iindeks th = i + 1, (k + RandNum50() + RandNum50() - 1) mod (100 - k)indeks, dengan penghapusan, untuk k= 0,99?

Ini "mendorong" puncak RandNum50() + RandNum50()distribusi ke depan secara seragam.

_{Saya cukup yakin ini tidak tepat seperti yang saya nyatakan karena 0 index (1) tidak dapat diperoleh dari pilihan pertama dan saya tidak dapat dengan cepat melihat alternatif 1..50 + 1..50 penyesuaian yang menghasilkan 0 ..99.}

Memperbarui

Untuk memperbaiki masalah yang saya catat, saya secara efektif digunakan RandNum100seperti yang disebutkan dalam komentar pertanyaan untuk menginisialisasi koffset pertama secara acak .

Ini menghasilkan distribusi dengan gelombang yang signifikan di bagian depan.

Alih-alih maju dengan 1 saya menggunakan yang lain RandNum50untuk meningkatkan itu terlebih dahulu k. Ini menghasilkan hasil yang cukup acak bagi saya, tetapi masih tidak "benar-benar" acak, seperti yang dapat dengan mudah dilihat jika Anda mengubah K menjadi 2.

Menguji kode VB.NET di mana saya melayani bahkan K. Catatan itu adalah O (K), 6K + 2 sebenarnya.