Temu duga pengekodan: Bagaimanakah anda melaksanakan shuffle tatasusunan in-place yang seragam?

Masalah dan konteks

Laksanakan reset() untuk memulihkan susunan asal dan shuffle() untuk mengembalikan pilih atur rawak yang seragam. Soalan ini menguji algoritma terawak, pertukaran in-place, sempadan nombor rawak, dan kebolehujian; corak yang sama muncul dalam pensampelan, cabutan undi, dan lekapan ujian (test fixtures).

Perkara yang diuji oleh penemu duga

• Memilih Fisher–Yates berbanding menukar kedudukan rawak sebarangan secara berulang kali.
• Mensampel indeks i hanya daripada bahagian yang belum ditetapkan (fixed).
• Membezakan API rawak inklusif dan separuh terbuka untuk mengelakkan berat sebelah (bias) atau limpahan (overflow).
• Mengekalkan garis dasar tak boleh ubah (immutable baseline) supaya reset() tidak terjejas oleh shuffle.
• Menerangkan masa O(n), ruang tambahan O(1), dan keseragaman.
• Membincangkan PRNG berbiji (seeded PRNGs), tatasusunan kosong, nilai pendua, dan had ujian statistik.

Soalan penjelasan untuk ditanya

• Patutkah shuffle() mengembalikan tatasusunan baharu atau mengubah dan mengembalikan tatasusunan kerja?
• Adakah reset() mesti mengembalikan salinan defensif supaya pemanggil tidak boleh mengubah keadaan dalaman?
• Adakah sumber rawak boleh disuntik, atau adakah sumber yang selamat secara kriptografi diperlukan?
• Adakah nilai pendua dibenarkan, dan adakah nilai yang sama pada kedudukan berbeza dianggap sebagai pilih atur yang berbeza?
• Adakah kita memerlukan keselamatan bebenang (thread safety), biji yang boleh dihasilkan semula, atau ketidakpastian kriptografi?
• Adakah input memerlukan penstriman atau ruang tambahan malar?

Kerangka jawapan 30 saat

“Saya menyimpan snapshot asal dan tatasusunan kerja. Untuk i dari indeks terakhir turun ke satu, saya mensampel j yang seragam dalam [0, i] dan menukar a[i] dengan a[j]. Setiap laluan menetapkan satu kedudukan, jadi masa jalanan ialah O(n) dan ruang tambahan ialah O(1). reset() mengembalikan salinan snapshot; sumber rawak boleh disuntik untuk kebolehulangan dan ujian statistik.”

Penelitian mendalam langkah demi langkah

Langkah 1: Mengasingkan keadaan. Salin input ke dalam original dan working; reset() menyalin original sekali lagi supaya rujukan luaran tidak dapat mengubah garis dasar.

Langkah 2: Tentukan batas rawak. Biarkan i berkurang dari n - 1 ke 1. Dengan API separuh terbuka panggil randomInt(i + 1) untuk mendapatkan 0..i; dengan API inklusif hantar 0 dan i secara eksplisit.

Langkah 3: Tukar in-place. Tukar working[i] dan working[j]; kedudukan i kini ditetapkan dan tiada tatasusunan sementara bersaiz sama dicipta.

Langkah 4: Terangkan keseragaman. Kedudukan tetap pertama mempunyai n pilihan yang sama berkemungkinan, kedudukan seterusnya mempunyai n-1, dan seterusnya, menghasilkan n! laluan pilihan yang sama berkemungkinan. Sumber rawak mestilah seragam bagi setiap indeks calon.

Langkah 5: Kendalikan pendua. Algoritma ini adalah seragam ke atas kedudukan elemen. Nilai berulang boleh menyebabkan beberapa pilih atur kedudukan dipaparkan sebagai jujukan nilai yang sama; jujukan yang kelihatan tidak sama dengan pilih atur kedudukan.

Langkah 6: Laksanakan reset. Kembalikan salinan original dan bina semula working; mendedahkan tatasusunan dalaman akan membolehkan pemanggil mencipta alias dan merosakkan garis dasar.

Langkah 7: Sahkan dan nyatakan kerumitan. Gunakan biji tetap untuk kebolehulangan, senaraikan kekerapan tatasusunan kecil untuk keseragaman anggaran, dan uji tatasusunan kosong serta tatasusunan satu elemen. Setiap shuffle mengambil masa O(n) dan ruang tambahan O(1); snapshot yang disimpan itu sendiri menggunakan keadaan O(n).

Jawapan model

“Saya mengekalkan tatasusunan original dan working. shuffle mengulangi i = n-1..1, mengambil j ∈ [0,i] yang seragam, dan menukar kedua-dua entri tersebut; reset mengembalikan salinan original dan membina semula working. Menukar kedudukan rawak sebarangan secara berulang boleh menulis ganti kedudukan terdahulu dan menghasilkan pilih atur yang berat sebelah. Fisher–Yates hanya mensampel awalan yang belum ditetapkan, jadi setiap pilih atur kedudukan adalah sama berkemungkinan. Ia berjalan dalam masa O(n) dan tidak memerlukan tatasusunan tambahan selain snapshot keadaan. Saya akan menyuntik sumber rawak untuk ujian berbiji dan menggantikannya dengan CSPRNG apabila hasilnya mempengaruhi keselamatan atau keadilan.”

Kesilapan lazim

• Mensampel [0,n-1] setiap pusingan → kedudukan tetap ditukar semula → gunakan [0,i].
• Mengira floor(random * i) → indeks i tidak pernah dipilih → gunakan i + 1 sebagai batas separuh terbuka.
• Menukar pasangan rawak sebarangan sebanyak n kali → pilih atur tidak dijamin seragam → tetapkan satu kedudukan bagi setiap langkah Fisher–Yates.
• Mengembalikan rujukan dalaman yang sama dari reset → pemanggil boleh merosakkan garis dasar → kembalikan salinan defensif.
• Menganggap PRNG sebagai kerawakan yang selamat → keputusan cabutan mungkin boleh diramal → pilih CSPRNG untuk model ancaman.

Soalan susulan dan respons

Susulan 1: Mengapakah gelung boleh dijalankan ke hadapan sebaliknya?

Bentuk ke hadapan menetapkan i dengan mensampel daripada [i,n-1]; buktinya adalah simetri. Invariannya ialah setiap pilihan hanya datang dari kawasan yang belum ditetapkan.

Susulan 2: Bagaimanakah anda membuktikan keseragaman?

Kedudukan n-1 mempunyai n pilihan yang sama berkemungkinan, kedudukan n-2 mempunyai n-1, dan seterusnya. Oleh itu, setiap laluan pilihan lengkap mempunyai kebarangkalian 1/n!.

Susulan 3: Bagaimanakah anda menguji kerawakan?

Jalankan banyak percubaan pada tatasusunan kecil, bandingkan kekerapan pilih atur dengan toleransi, dan gunakan biji tetap untuk mengesahkan kebolehulangan. Sampel yang terhad adalah bukti pemerhatian, bukan bukti mutlak.

Susulan 4: Bilakah pseudo-rawak biasa tidak mencukupi?

Gunakan CSPRNG sistem apabila cabutan, token, atau shuffle mempengaruhi keselamatan atau hak kelayakan. PRNG berbiji sesuai untuk simulasi, permainan, dan ujian.

Susulan 5: Bagaimana jika input adalah senarai berpaut?

Penukaran kepada tatasusunan memerlukan ruang O(n). Pertukaran nod boleh mengekalkan storan tetapi capaian rawak menjadi mahal, jadi kekangan perlu dirundingkan semula.

Susulan 6: Bagaimanakah anda mengendalikan panggilan serentak?

Berikan setiap tika (instance) keadaan terasing dan kunci mutasi, atau kembalikan snapshot tak boleh ubah. Pemanggil tidak boleh melihat pertukaran separa semasa bebenang lain melakukan set semula.

Susulan 7: Adakah pustaka standard Java menggunakan idea ini?

Oracle mendokumentasikan lintasan ke belakang yang menukar elemen rawak ke dalam kedudukan semasa; dengan sumber yang adil, semua pilih atur berlaku dengan kebarangkalian yang sama.