Apakah ada algoritma "pengurutan" yang mengembalikan permutasi acak ketika menggunakan pembanding koin-balik?

Terinspirasi oleh pertanyaan ini di mana penanya ingin tahu apakah waktu berjalan berubah ketika pembanding yang digunakan dalam algoritma pencarian standar digantikan oleh flip koin yang adil, dan juga kegagalan Microsoft yang menonjol untuk menulis generator permutasi yang seragam, pertanyaan saya adalah demikian :

Apakah ada algoritma penyortiran berbasis perbandingan yang akan, tergantung pada implementasi kami dari pembanding:

1. kembalikan elemen dalam urutan yang diurutkan ketika menggunakan komparator sejati (yaitu, perbandingan melakukan apa yang kita harapkan dalam algoritma pengurutan standar)
2. mengembalikan permutasi acak seragam elemen ketika pembanding digantikan oleh flip koin yang adil (yaitu, kembali x < y = truedengan probabilitas 1/2, terlepas dari nilai x dan y)

Kode untuk algoritma pengurutan harus sama. Hanya kode di dalam "kotak hitam" perbandingan yang diizinkan untuk diubah.

Algoritma deterministik berikut (tanpa pembanding) bekerja untuk input tuple :$(a_1,\dots,a_n)$

1. Apakah yang Fisher-Yates mengocok menggunakan komparator Anda dengan beberapa pasangan statis (mengatakan ) sebagai flip koin (melakukan penerimaan-penolakan sampling). Jika komparator mengeluarkan 1 pertama kali, gunakan itu terbalik untuk menghindari loop penolakan tanpa akhir dalam kasus deterministik.$a_1 < a_2$$1$
2. (speedup opsional: Coba satu pasangan kali, di mana n adalah panjang atau input Anda. Jika ada dua output yang berbeda, kembalikan permutasi yang diperoleh dalam (1))$n$$n$
3. Sortir array Anda menggunakan sortir gabungan.

Diberikan relasi urutan deterministik sebagai pembanding, algoritma ini mengurutkan array dalam waktu karena shuffle Fisher-Yates berjalan dalam O ( n ) menggunakan maksimal O ( log n ) "acak bit" nonrandom (misalnya panggilan ke pembanding Anda ) pada setiap langkah dan gabungan, memiliki kompleksitas asimptotik yang sama. Hasil dari (1) sama sekali tidak berguna dalam kasus ini, tetapi karena diikuti oleh semacam nyata, ini tidak ada salahnya.$\mathcal{O}(n \log n)$$\mathcal{O}(n)$$\mathcal{O}(\log n)$

Diberikan flip koin nyata sebagai pembanding (1) memungkinkan array dengan probabilitas yang sama untuk setiap permutasi dan jika Anda benar-benar harus melakukan (3) (Anda ditinggalkan (2) atau (2) gagal menentukan keacakan), ini bukan salahnya karena distribusi hasil hanya tergantung pada urutan inputnya yang terdistribusi secara merata di antara semua permutasi karena (1), sehingga hasil dari seluruh algoritma juga terdistribusi secara seragam. Jumlah setiap pengambilan sampel penerimaan-penolakan harus diulang didistribusikan secara geometris (tolak dengan probabilitas ) dan karena itu memiliki nilai yang diharapkan<2. Setiap penggunaan pengulangan palinglognbit, sehingga analisis runtime hampir sama seperti dalam kasus deterministik, tetapi kami hanya mendapatkanruntime diharapkandariO(nlogn), dengan kemungkinan nontermination (Menghentikan hanyahampir pasti).$< \frac{1}{2}$$< 2$$\log n$$\mathcal{O}(n \log n)$

---

Seperti Joe menunjukkan: Jika Anda tidak menyukai tes untuk bit pertama dalam (1), melakukan (3) maka (1) dan menggunakan yang selalu 0 , karena array sudah diurutkan dalam kasus deterministik. Selain itu Anda harus mengurangi angka acak Anda dari batas atas pada rentang dalam loop, karena batas atas untuk angka acak menghasilkan permutasi yang sama. Namun ketahuilah bahwa (2) itu dilarang, karena Anda selalu harus melakukan shuffle dalam kasus tebusan.$a_n < a_1$$0$

---

Anda bahkan dapat menggunakan panggilan yang sama ke komparator Anda untuk (1) dan (3), tetapi kemudian membuktikan bahwa hasilnya didistribusikan secara merata setidaknya jauh lebih sulit, jika mungkin sama sekali.

---

Algoritme berikut tidak memiliki fase berbeda untuk mengocok dan mengurutkan, tetapi secara asimptot lebih lambat. Ini pada dasarnya semacam penyisipan dengan pencarian biner . Saya akan menggunakan untuk menunjukkan input dan b k = ( b k , 1 , ... , b k , k ) untuk menunjukkan hasil setelah putaran ke- k :$a=(a_1,\dots,a_n)$$b_k=(b_{k,1},\dots,b_{k,k})$$k$

1. Set $b_{1,1} = a_1$
2. Jika maka b 2 = ( a 2 , a 1 ) dan ( c , d ) : = ( 2 , 1 ) lain b 2 = ( a 1 , a 2 ) dan ( c , d ) : = ( 1 , 2 ) . Dalam kedua kasus a d$a_2 < a_1$$b_2 = (a_2,a_1)$$(c,d):= (2,1)$$b_2 = (a_1,a_2)$$(c,d):= (1,2)$ akan selalu menjadi 0 (mis. salah) untuk pembanding nonrandom.$a_d < a_c$$0$
3. Untuk mendapatkan untuk k ≥ 3, dapatkan b k - 1 terlebih dahulu.$b_{k}$$k \geq 3$$b_{k-1}$
4. Mari dan k ' = 2 l , yaitu k ' adalah kekuatan paling 2 tidak lebih kecil dari k .$l=\lceil log_2 k \rceil$$k' = 2^l$$k'$$2$$k$
5. Biarkan . Untuk setiap j ∈ { 1 , … , l } biarkan aku j = { i j - 1 + 2 l - j i j - 1 + 2 l - j > k - 1 ∧ a d < a c i j - 1 i j - 1 + 2 l $i_0 = 0$$j \in \{1,\dots,l\}$ $$i_j = \begin{cases} i_{j-1} + 2^{l-j} & i_{j-1} + 2^{l-j} > k-1 \wedge a_d < a_c\\ i_{j-1} & i_{j-1} + 2^{l-j} > k-1 \wedge \neg (a_d < a_c)\\ i_{j-1} + 2^{l-j} & i_{j-1} + 2^{l-j} \leq k-1 \wedge b_{k-1,i_{j-1} + 2^{l-j}} < a_k \\ i_{j-1} & i_{j-1} + 2^{l-j} \leq k-1 \wedge \neg(b_{k-1,i_{j-1} + 2^{l-j}} < a_k) \\ \end{cases}$$
6. $i_l > k$$b_k=(b_{k-1,1},\dots,b_{k-1,i_l -1},a_k,b_{k-1,i_l},\dots,b_{k-1,k-1})$
7. $b_n$

$k-1$$k$

Perhatikan bahwa algoritma ini tidak efisien dalam kedua mode dibandingkan dengan pengocokan dan gabungan jenis Fisher-Yates karena memasukkan elemen ke posisi sewenang-wenang mahal jika menggunakan array dan pencarian biner membutuhkan waktu linier jika menggunakan daftar. Tapi mungkin modifikasi heap sort atau tree sort dengan cara yang sama dapat menghasilkan algoritma yang lebih cepat.

$n \leq 2$$A/2^B$$1/n!$$n > 2$$1/n!$$A/2^B$