Acak untuk mencakup semua kemungkinan permutasi

Objek Random dalam kerangka .NET mengambil bilangan bulat 32 bit sebagai benih. Ini berarti algoritma pengacakan apa pun yang menggunakan objek Random dibatasi (paling banyak) 4 miliar kemungkinan pengacakan (dengan asumsi pengacakan bersifat deterministik sesuai dengan urutan acak, yang saya tidak dapat membayangkan mengapa hal itu tidak terjadi). Artinya, jika koleksi melebihi 13 elemen, maka dijamin pengacakan tidak akan mencakup semua kemungkinan permutasi. Ketika ukuran koleksi semakin jauh dari ukuran ini, subkumpulan kemungkinan permutasi yang dicakup oleh pengocokan menjadi semakin tidak signifikan.

4 miliar adalah angka (secara subyektif) besar, tetapi jika Anda membuat beberapa permutasi "acak" dari suatu koleksi, kemungkinan duplikat menjadi jauh lebih besar dari yang seharusnya (terutama jika Anda mempertimbangkan paradoks ulang tahun/prinsip lubang merpati).

Apakah ada cara sederhana untuk mengatasi hal ini yang tidak melibatkan saya menerapkan generator nomor acak saya sendiri?


person Patrick M    schedule 01.07.2014    source sumber
comment
Menarik, jadi cakupan kasus terbaiknya adalah 4bil^n di mana n adalah berapa kali saya mengacak. Satu-satunya masalah adalah jika pengocokannya sangat cepat saya mungkin perlu tidur selama beberapa milidetik untuk memastikan benihnya berbeda.   -  person Patrick M    schedule 01.07.2014
comment
Anda dapat mempertimbangkan untuk menggunakan API online Random.org untuk pembuatan acak, jika aplikasi/proyek Anda cocok; hanya dua sen saya.   -  person Lexicon    schedule 01.07.2014
comment
Jika Anda menggunakan ini misalnya. tujuan bermain game, Anda mungkin harus beralih ke RNG yang aman secara kriptografis.   -  person Damien_The_Unbeliever    schedule 01.07.2014
comment
Bagilah dan taklukkan: int digitNum = 10; panjang aku = 0; Random r = new Random(DateTime.Now.Millisecond); for (int i = 0; i ‹ digitNum; i++) l += r.Next(0, 9) * (long)Math.Pow((double)10, (double)i);   -  person Johnny    schedule 01.07.2014
comment
Perhatikan bahwa DateTime.Millisecond hanya dapat berubah setiap beberapa milidetik, bergantung pada sistem.   -  person Matthew Watson    schedule 01.07.2014
comment
bukankah algoritma pengacakan Fisher – Yates akan menyelesaikan masalah Anda?   -  person Felice Pollano    schedule 01.07.2014
comment
ericlippert.com/2013/05/06/producing-permutations-part -tujuh. Kalau dipikir-pikir, Anda harus membaca keseluruhan serinya mulai dari ericlippert .com/2013/04/15/producing-permutations-part-one. Di dalamnya, ia menunjukkan cara mengubah bilangan acak menjadi permutasi.   -  person Jim Mischel    schedule 01.07.2014


Jawaban (2)


Saya tidak akan merekomendasikan membuat generator nomor acak (RNG) Anda sendiri. Teori dibalik mereka cukup kuat. Jika Anda memerlukan sesuatu yang 'lebih acak' maka Anda perlu menggunakan RNG yang aman secara kriptografis. Untuk menggunakan generator default yang disediakan oleh .Net framework:

menggunakan Sistem.Keamanan.Kriptografi;

var generator = RandomNumberGenerator.Create();

Anda dapat menggunakan ini untuk mendapatkan beberapa byte acak yang dapat Anda konversi menjadi int, atau tipe nilai lainnya.

person Ananke    schedule 01.07.2014

Anda dapat menggunakan salah satu port Mersenne Twister ke C#. MT19937 memiliki ruang status 19937 bit, dan meskipun Anda dapat memilih untuk menyemainya dengan int tunggal, penyemaian status penuh juga tersedia jika Anda memiliki sumber entropi yang sesuai untuk memberinya makan.

person pjs    schedule 01.07.2014