Apa cara terbaik untuk mengacak urutan daftar generik dalam C #? Saya punya satu set terbatas dari 75 angka dalam daftar yang ingin saya berikan urutan acak, untuk menggambar mereka untuk aplikasi jenis lotre.
c#
generic-list
mirezus
sumber
sumber
Jawaban:
Acak apa saja
(I)List
dengan metode ekstensi berdasarkan shuffle Fisher-Yates :Pemakaian:
Kode di atas menggunakan metode System.Random yang banyak dikritik untuk memilih calon swap. Ini cepat tetapi tidak acak sebagaimana mestinya. Jika Anda membutuhkan kualitas keacakan yang lebih baik dalam shuffles Anda, gunakan penghasil angka acak dalam System.Security.Cryptography seperti:
Perbandingan sederhana tersedia di blog ini (WayBack Machine).
Sunting: Sejak menulis jawaban ini beberapa tahun yang lalu, banyak orang berkomentar atau menulis kepada saya, untuk menunjukkan kelemahan besar yang konyol dalam perbandingan saya. Mereka tentu saja benar. Tidak ada yang salah dengan System.Random jika digunakan seperti yang dimaksudkan. Dalam contoh pertama saya di atas, saya instantiate variabel rng di dalam metode Shuffle, yang meminta masalah jika metode ini akan dipanggil berulang kali. Di bawah ini adalah contoh lengkap dan tetap berdasarkan komentar yang sangat berguna yang diterima hari ini dari @weston di sini di SO.
Program.cs:
sumber
Random rng = new Random();
sebuahstatic
akan memecahkan masalah di pos perbandingan. Karena setiap panggilan berikutnya akan mengikuti dari panggilan sebelumnya hasil acak terakhir.Jika kita hanya perlu mengacak item dalam urutan yang benar-benar acak (hanya untuk mencampur item dalam daftar), saya lebih suka kode sederhana namun efektif ini yang memesan item dengan panduan ...
sumber
var shuffledcards = cards.OrderBy(a => rng.Next());
compilr.com/grenade/sandbox/Program.csNewGuid
hanya menjamin bahwa itu memberi Anda GUID unik. Itu tidak membuat jaminan tentang keacakan. Jika Anda menggunakan GUID untuk tujuan selain membuat nilai unik , Anda salah melakukannya.Saya sedikit terkejut dengan semua versi kikuk dari algoritma sederhana ini di sini. Fisher-Yates (atau Knuth shuffle) agak rumit tetapi sangat kompak. Mengapa ini rumit? Karena Anda perlu memperhatikan apakah generator angka acak Anda
r(a,b)
mengembalikan nilai di manab
inklusif atau eksklusif. Saya juga mengedit deskripsi Wikipedia sehingga orang tidak secara buta mengikuti kodesemu di sana dan membuat sulit untuk mendeteksi bug. Untuk .Net,Random.Next(a,b)
mengembalikan nomor eksklusifb
tanpa basa-basi lagi, inilah cara penerapannya di C # /. Net:Coba kode ini .
sumber
i = list.Count - 1
, yaitu iterasi terakhir,rnd.Next(i, list.Count)
akan memberikan Anda kembali. Karena itu Anda perlui < list.Count -1
sebagai kondisi loop. Nah, Anda tidak 'membutuhkannya', tetapi menghemat 1 iterasi;)Metode ekstensi untuk IEnumerable:
sumber
OrderBy
menggunakan varian QuickSort untuk mengurutkan item dengan kunci (seolah-olah acak). Kinerja QuickSort adalah O (N log N) ; sebaliknya, shuffle Fisher-Yates adalah O (N) . Untuk koleksi 75 elemen, ini mungkin bukan masalah besar, tetapi perbedaannya akan menjadi nyata untuk koleksi yang lebih besar.Random.Next()
dapat menghasilkan distribusi nilai pseudo-acak yang cukup, tetapi tidak menjamin bahwa nilai tersebut akan unik. Peluang kunci duplikat tumbuh (non-linear) dengan N hingga mencapai kepastian ketika N mencapai 2 ^ 32 + 1. TheOrderBy
QuickSort adalah stabil semacam; dengan demikian, jika beberapa elemen terjadi untuk mendapatkan nilai indeks pseudo-acak yang sama, maka urutannya dalam urutan output akan sama seperti pada urutan input; dengan demikian, bias dimasukkan ke dalam "shuffle".Ide mendapatkan objek anonim dengan item dan urutan acak lalu menyusun ulang item berdasarkan urutan dan nilai pengembalian ini:
sumber
sumber
var listCopy = list.ToList()
untuk menghindari mengeluarkan semua item dari daftar yang masuk? Saya tidak benar-benar mengerti mengapa Anda ingin bermutasi dari daftar tersebut menjadi kosong.EDIT The
RemoveAt
adalah kelemahan dalam versi sebelumnya. Solusi ini mengatasi itu.Perhatikan opsional
Random generator
, jika implementasi kerangka dasarRandom
tidak aman atau kriptografis cukup kuat untuk kebutuhan Anda, Anda dapat menyuntikkan implementasi Anda ke dalam operasi.Implementasi yang sesuai untuk implementasi thread-safe yang secara cryptographically kuat
Random
dapat ditemukan dalam jawaban ini.Inilah sebuah ide, perluas IList dengan cara (semoga) efisien.sumber
GetNext
atauNext
?Anda dapat mencapainya dengan menggunakan metode ekstensi sederhana ini
dan Anda dapat menggunakannya dengan melakukan hal berikut
sumber
Random
instance kelas di luar fungsi sebagaistatic
variabel. Kalau tidak, Anda mungkin mendapatkan seed pengacakan yang sama dari timer jika dipanggil secara berurutan.Ini adalah metode shuffle pilihan saya ketika diinginkan untuk tidak memodifikasi yang asli. Ini adalah varian dari algoritma Fisher-Yates "inside-out" yang bekerja pada urutan enumerable apa pun (panjangnya
source
tidak perlu diketahui dari awal).Algoritma ini juga dapat diimplementasikan dengan mengalokasikan rentang dari
0
hinggalength - 1
dan melelahkan indeks secara acak dengan menukar indeks yang dipilih secara acak dengan indeks terakhir sampai semua indeks telah dipilih tepat sekali. Kode di atas menyelesaikan hal yang sama persis tetapi tanpa alokasi tambahan. Yang cukup rapi.Berkenaan dengan
Random
kelas itu adalah generator nomor tujuan umum (dan Jika saya menjalankan lotre saya akan mempertimbangkan menggunakan sesuatu yang berbeda). Itu juga bergantung pada nilai seed berdasarkan waktu secara default. Pengurangan kecil dari masalahnya adalah dengan menaburkanRandom
kelas denganRNGCryptoServiceProvider
atau Anda dapat menggunakanRNGCryptoServiceProvider
dalam metode yang mirip dengan ini (lihat di bawah) untuk menghasilkan nilai titik mengambang ganda acak yang dipilih secara seragam, tetapi menjalankan lotre cukup banyak membutuhkan pemahaman keacakan dan sifat dari sumber keacakan.Titik menghasilkan dobel acak (antara 0 dan 1 secara eksklusif) adalah menggunakan skala untuk solusi integer. Jika Anda perlu mengambil sesuatu dari daftar berdasarkan pada double acak
x
yang selalu akan0 <= x && x < 1
lurus ke depan.Nikmati!
sumber
Jika Anda tidak keberatan menggunakan dua
Lists
, maka ini mungkin cara termudah untuk melakukannya, tetapi mungkin bukan yang paling efisien atau tidak dapat diprediksi:sumber
Jika Anda memiliki nomor tetap (75), Anda bisa membuat array dengan 75 elemen, lalu menghitung daftar Anda, memindahkan elemen ke posisi acak dalam array. Anda dapat menghasilkan pemetaan nomor daftar untuk indeks array menggunakan shuffle Fisher-Yates .
sumber
Saya biasanya menggunakan:
sumber
sumber
Berikut adalah Shuffler yang efisien yang mengembalikan array byte dari nilai-nilai yang diacak. Itu tidak pernah mengocok lebih dari yang dibutuhkan. Itu dapat dimulai kembali dari tempat sebelumnya. Implementasi aktual saya (tidak diperlihatkan) adalah komponen MEF yang memungkinkan pengocok pengganti yang ditentukan pengguna.
`
sumber
Berikut cara aman untuk melakukannya:
sumber
sumber
Modifikasi sederhana dari jawaban yang diterima yang mengembalikan daftar baru alih-alih bekerja di tempat, dan menerima yang lebih umum
IEnumerable<T>
seperti metode Linq lainnya.sumber
Saya telah menemukan solusi online yang menarik.
Courtesy: https://improveandrepeat.com/2018/08/a-simple-way-to-shuffle-your-lists-in-c/
var mengocok = myList.OrderBy (x => Guid.NewGuid ()). ToList ();
sumber
Posting lama pasti, tapi saya hanya menggunakan GUID.
GUID selalu unik, dan karena itu dibuat ulang setiap kali hasilnya berubah setiap kali.
sumber
Pendekatan yang sangat sederhana untuk masalah semacam ini adalah dengan menggunakan sejumlah swap elemen acak dalam daftar.
Dalam pseudo-code ini akan terlihat seperti ini:
sumber