Algoritma yang efisien untuk menghasilkan dua permutasi multiset yang tersebar dan acak secara acak

Latar Belakang

$\newcommand\ms[1]{\mathsf #1}\def\msD{\ms D}\def\msS{\ms S}\def\mfS{\mathfrak S}\newcommand\mfm[1]{#1}\def\po{\color{#f63}{\mfm{1}}}\def\pc{\color{#6c0}{\mfm{c}}}\def\pt{\color{#08d}{\mfm{2}}}\def\pth{\color{#6c0}{\mfm{3}}}\def\pf{4}\def\pv{\color{#999}5}\def\gr{\color{#ccc}}\let\ss\gr$ Misalkan saya punya dua batch identik kelereng. Setiap marmer bisa menjadi salah satu warna , di mana . Biarkan menunjukkan jumlah kelereng warna dalam setiap batch. $n$ $c$ $c≤n$ $n_i$ $i$

Biarkan $\msS$ menjadi multiset $\small\{\overbrace{\po,…,\po}^{n_1},\;\overbrace{\pt,…,\pt}^{n_2},\;…,\;\overbrace{\vphantom 1\pc,…,\pc}^{n_c}\}$ mewakili satu kumpulan. Dalam representasi frekuensi , $\msS$ juga dapat ditulis sebagai $(\po^{n_1} \;\pt^{n_2}\; … \;\pc^{n_c})$ .

Jumlah permutasi yang berbeda dari $\msS$ diberikan oleh multinomial :

| S_{S} | = (\binom{n}{n_{1}, n_{2}, \dots, n_{c}}) = \frac{n!}{n_{1}! n_{2}! \dots n_{c}!} = n! \prod_{i = 1}^{c} \frac{1}{n_{i}!} .

$\left|\mfS_{\msS}\right|=\binom{n}{n_1,n_2,\dots,n_c}=\frac{n!}{n_1!\,n_2!\cdots n_c!}=n! \prod_{i=1}^c \frac1{n_i!}.$

Pertanyaan

Apakah ada algoritma yang efisien untuk menghasilkan dua permutasi difus, deranged $P$ dan $Q$ dari $\msS$ secara acak? (Distribusi harus seragam.)

Sebuah permutasi $P$ adalah difus jika untuk setiap elemen yang berbeda $i$ dari $P$ , contoh dari $i$ spasi kira-kira merata di $P$ .
Sebagai contoh, misalkan $\msS=(\po^4\;\pt^4)=\{\po,\po,\po,\po,\pt,\pt,\pt,\pt\}$ .
- $\{\po, \po, \po, \pt, \pt, \pt, \pt, \po\}$ tidak tersebar
- $\{\po, \pt, \po, \pt, \po, \pt, \po, \pt\}$ tersebar
Lebih teliti:
- Jika , hanya ada satu contoh dari untuk "spasi" di , jadi mari . $n_i=1$ $i$ $P$ $\Delta(i)=0$
- Jika tidak, biarkan menjadi jarak antara contoh dan contoh dari di . Kurangi darinya jarak yang diharapkan antara instance , tentukan yang berikut: Jika ditempatkan secara merata dalam , maka harus nol, atau sangat dekat dengan nol jika . $d(i,j)$ $j$ $j+1$ $i$ $P$ $i$ $δ (i, j) = d (i, j) - \frac{n}{n_{i}} Δ (i) = \sum_{j = 1}^{n_{i} - 1} δ (i, j)^{2}$ $\delta(i,j)=d(i,j)-\frac n{n_i}\qquad\qquad\Delta(i)=\sum_{j=1}^{n_i-1} \delta(i,j)^2$ $i$ $P$ $\Delta(i)$ $n_i\nmid n$
Sekarang menentukan statistik untuk mengukur berapa banyak setiap yang merata spasi di . Kami menyebut difus jika mendekati nol, atau kira-kira . (Seseorang dapat memilih ambang khusus untuk sehingga menyebar jika ) $s(P)=\sum_{i=1}^c\Delta(i)$ $i$ $P$ $P$ $s(P)$ $s(P)\ll n^2$ $k\ll1$ $\msS$ $P$ $s(P)<kn^2$

Batasan ini mengingatkan masalah penjadwalan real-time yang lebih ketat yang disebut masalah pinwheel dengan multiset (sehingga ) dan kepadatan . Tujuannya adalah untuk menjadwalkan urutan siklik tak terbatas sedemikian rupa sehingga setiap urutan panjang berisi setidaknya satu instance dari . Dengan kata lain, jadwal yang layak membutuhkan semua ; jika padat ( ), maka dan . Masalah kincir tampaknya NP-lengkap. $\ms A=n/\msS$ $a_i=n/n_i$ $\rho=\sum_{i=1}^c n_i/n=1$ $P$ $a_i$ $i$ $d(i,j)≤a_i$ $\ms A$ $\rho= 1$ $d(i,j)=a_i$ $s(P)=0$
Dua permutasi dan yang gila jika adalah kekacauan dari ; yaitu, untuk setiap indeks . $P$ $Q$ $P$ $Q$ $P_i ≠ Q_i$ $i\in[n]$
Sebagai contoh, misalkan . $\msS=(\po^2\;\pt^2)=\{\po,\po,\pt,\pt\}$
- $\{\po, \pt, \po, \pt\}$ dan tidak gila $\{\po, \po, \pt, \pt\}$
- $\{\po, \pt, \po, \pt\}$ dan kacau $\{\pt, \po, \pt, \po\}$

Analisis eksplorasi

Saya tertarik pada keluarga multiset dengan dan untuk . Khususnya, mari . $n=20$ $n_i=4$ $i\lesssim4$ $\msD=(\gr1^4\,\gr2^4\,\gr3^4\,\gr4^3\,\gr5^2\,\gr6^1\,\gr7^1\,\gr8^1)$

Probabilitas bahwa dua permutasi acak dan dari yang gila adalah sekitar 3%. $P$ $Q$ $\msD$

Ini dapat dihitung sebagai berikut, di mana adalah ke : Lihat di sini untuk penjelasan. $L_k$ $k$
$\begin{aligned} | D_{D} | & = \int_{0}^{\infty} d t e^{- t} \prod_{i = 1}^{c} L_{n_{i}} (t) = \int_{0}^{\infty} d t e^{- t} (L_{4} (t))^{3} (L_{3} (t)) (L_{2} (t)) (L_{1} (t))^{3} \\ = 4.5 \times 10^{11} \\ | S_{D} | & = n! \prod_{i = 1}^{c} \frac{1}{n_{i}!} = \frac{20!}{(4!)^{3} (3!) (2!) (1!)^{3}} = 1.5 \times 10^{13} \\ p & = | D_{D} | / | S_{D} | \approx 0.03 \end{aligned}$ $\begin{align*} \left|{\mathfrak D}_{\msD}\right| &=\int_0^\infty \!\!dt\; e^{-t}\, \prod_{i=1}^c L_{n_i}(t) =\int_0^\infty \!\!dt\; e^{-t}\, \bigl(L_4(t)\bigr)^3\bigl(L_3(t)\bigr)\bigl(L_2(t)\bigr)\bigl(L_1(t)\bigr)^3\\ &=4.5\times10^{11}\\ \left|\mfS_{\msD}\right| &=n!\prod_{i=1}^c \frac1{n_i!} =\frac{20!}{(4!)^3\,(3!)\,(2!)\,(1!)^3} =1.5\times10^{13}\\ p&=\left|{\mathfrak D}_{\msD}\right|/ \left|\mfS_{\msD}\right|\approx0.03\end{align*}$
Probabilitas bahwa permutasi acak dari adalah difus adalah sekitar 0,01%, pengaturan ambang sewenang-wenang pada kira-kira . $P$ $\msD$ $s(P)<25$

Di bawah ini adalah plot probabilitas empiris 100.000 sampel mana adalah permutasi acak dari . $s(P)$ $P$ $\msD$

Pada ukuran sampel sedang, . $s(P)\sim \text{Gamma}(\alpha\approx8,\beta\approx18)$

$\begin{array}{ccl} P & s (P) & cdf (s (P)) \\ {1, 8, 2, 3, 4, 1, 5, 2, 3, 6, 1, 4, 2, 3, 7, 1, 5, 2, 4, 3} & \frac{11}{9} \approx 1 & < 10^{- 5} \\ {8, 2, 3, 4, 1, 6, 5, 2, 3, 4, 1, 7, 1, 2, 3, 5, 4, 1, 2, 3} & \frac{140}{9} \approx 16 & < 10^{- 4} \\ {3, 6, 5, 1, 3, 4, 2, 1, 2, 7, 8, 5, 2, 4, 1, 3, 3, 2, 1, 4} & \frac{650}{9} \approx 72 & 0.05 \\ {3, 1, 3, 4, 8, 2, 2, 1, 1, 5, 3, 3, 2, 6, 4, 4, 2, 1, 7, 5} & \frac{1223}{9} \approx 136 & 0.45 \\ {4, 1, 1, 4, 5, 5, 1, 3, 3, 7, 1, 2, 2, 4, 3, 3, 8, 2, 2, 6} & \frac{1697}{9} \approx 189 & 0.80 \end{array}$ $\begin{array}{ccl}\renewcommand\mfm[1]{\textbf{#1}} \hline P & s(P) & \text{cdf}(s(P)) \\ \hline \{\po, \ss8, \pt, \pth, \pf, \po, \pv, \pt, \pth, \ss6, \po, \pf, \pt, \pth, \ss7, \po, \pv, \pt, \pf, \pth\} & \frac{11}9\approx1\, & <10^{-5} \\ \{\ss8, \pt, \pth, \pf, \po, \ss6, \pv, \pt, \pth, \pf, \po, \ss7, \po, \pt, \pth, \pv, \pf, \po, \pt, \pth\} & \frac{140}9\approx16 & <10^{-4} \\ \{\pth, \ss6, \pv, \po, \pth, \pf, \pt, \po, \pt, \ss7, \ss8, \pv, \pt, \pf, \po, \pth, \pth, \pt, \po, \pf\} & \frac{650}9\approx72 & \phantom{<1}0.05 \\ \{\pth, \po, \pth, \pf, \ss8, \pt, \pt, \po, \po, \pv, \pth, \pth, \pt, \ss6, \pf, \pf, \pt, \po, \ss7, \pv\} & \frac{1223}9\approx136 & \phantom{<1}0.45 \\ \{\pf, \po, \po, \pf, \pv, \pv, \po, \pth, \pth, \ss7, \po, \pt, \pt, \pf, \pth, \pth, \ss8, \pt, \pt, \ss6\} & \frac{1697}9\approx189 & \phantom{<1}0.80 \\ \hline \end{array}$

Probabilitas bahwa dua permutasi acak adalah valid (baik difus dan deranged) adalah sekitar . $v\approx(0.03)(0.0001)^2\approx10^{-10}$

Algoritma tidak efisien

Algoritme "cepat" yang umum untuk menghasilkan kekacauan acak dari set adalah berbasis penolakan:

lakukan
     P ← random_permutation ( D )
sampai is_derangement ( D , P )
return P

yang mengambil sekitar iterasi, karena ada sekitar mungkin derangements. Namun algoritma acak berbasis-penolakan tidak akan efisien untuk masalah ini, karena akan mengambil urutan iterasi . $e$ $n!/e$ $1/v\approx10^{10}$

Dalam algoritma yang digunakan oleh Sage , kekacauan acak dari multiset "dibentuk dengan memilih elemen secara acak dari daftar semua kemungkinan kekacauan." Namun ini juga tidak efisien, karena ada permutasi yang valid untuk dicacah, dan selain itu, seseorang akan memerlukan algoritma untuk melakukan hal itu. $v\,|\mfS_{\msD}|^2\approx10^{16}$

Pertanyaan lebih lanjut

Apa kompleksitas masalah ini? Bisakah itu direduksi menjadi paradigma yang sudah dikenal, seperti aliran jaringan, pewarnaan grafik, atau pemrograman linier?

algorithms combinatorics probability-theory permutations sampling hftf
sumber

Mengenai definisi Anda tentang "spasi", jangan Anda inginkan untuk dengan sebagai penjaga? Dengan kata lain, elemen tunggal harus di tengah, dua harus mempartisi permutasi dalam pertiga, dan seterusnya.

d (i, j) - n / (n_{i} + 1)

$d(i,j) - n/(n_i + 1)$

0 \leq i \leq j \leq n + 1

$0 \leq i \leq j \leq n+1$

P_{0} = P_{n + 1} = i

$P_0 = P_{n+1} = i$

Raphael

Apa yang terjadi jika untuk evil (kecil, tetapi cukup besar); apakah kita bahkan memiliki permutasi difus daripada? Kami tentu tidak tahan untuk menemukan dua yang gila! Tampaknya tidak ada elemen yang dapat terjadi lebih dari kali.

S = {1^{n - k}, 2^{k}}

$S = \{ 1^{n-k}, 2^k\}$

k

$k$

n / 2

$n/2$

Raphael

Berapa rasio dari semua pasangan permutasi yang rusak di antara semua pasangan permutasi difus ? Demikian pula, dari semua pasangan permutasi gila, berapa banyak yang terdiri dari dua yang tersebar? (Jika salah satu rasio "tinggi", kita dapat memusatkan upaya kita pada satu setengah dari proses, meninggalkan yang lain pada penolakan.)

Raphael

@Raphael (# 3a) Dari 1 juta permutasi acak

, 561 yang difus ini memiliki

D

$\mathsf D$

s (P) \leq 30

$s(P)\le 30$

dari pasangan yang gila.

6118 / (\binom{561}{2}) = 6118 / 157080 \approx 3.9 %

$6118/\binom{561}{2}=6118/157080\approx3.9\%$

hftf

@Raphael (# 3b) Dari 10 juta pasang permutasi acak

, 306893 pasang rusak. Hanya 29 pasangan yang memiliki permutasi dengan

. Berikut ini adalah histogram ( nilai ).

D

$\mathsf D$

s (P) \leq 50

$s(P)\le50$

hftf

Jawaban:

Satu pendekatan: Anda dapat menguranginya menjadi masalah berikut: Diberikan rumus boolean , pilih tugas seragam secara acak dari antara semua tugas memuaskan . Masalah ini NP-hard, tetapi ada algoritma standar untuk menghasilkan yang kira-kira terdistribusi secara merata, metode pinjaman dari algoritma #SAT. Sebagai contoh, satu teknik adalah untuk memilih fungsi hash yang rentangnya memiliki ukuran yang dipilih dengan hati-hati (sekitar ukuran yang sama dengan jumlah penugasan yang memuaskan ), pilih secara seragam secara acak nilai dari dalam kisaran $\varphi(x)$ $x$ $\varphi(x)$ $x$ $h$ $\varphi$ $y$ , dan kemudian menggunakan pemecah SAT untuk menemukan tugas yang memuaskan untuk rumus . Untuk membuatnya efisien, Anda dapat memilih menjadi peta linier yang jarang. $h$ $\varphi(x) \land (h(x)=y)$ $h$

Ini mungkin menembakkan kutu dengan meriam, tetapi jika Anda tidak memiliki pendekatan lain yang tampaknya bisa diterapkan, ini adalah salah satu yang bisa Anda coba.

DW
sumber

menemukan ini sulit untuk diikuti.

adalah nilai boolean dan

adalah string biner (himpunan variabel biner)? jadi persamaan terakhir berarti ...?

φ (x)

$\varphi(x)$

h (x)

$h(x)$

vzn

beberapa diskusi / analisis yang diperluas dari masalah ini dimulai dalam obrolan cs dengan latar belakang lebih lanjut yang mengungkap beberapa subjektivitas dalam persyaratan masalah yang kompleks tetapi tidak menemukan kesalahan atau kekeliruan yang terang-terangan. ¹

di sini adalah beberapa kode yang diuji / dianalisis yang, dibandingkan dengan solusi lain berdasarkan SAT relatif "cepat dan kotor" tetapi nontrivial / rumit untuk debug. ini secara longgar didasarkan pada skema optimasi pseudorandom / serakah lokal yang agak mirip dengan misalnya 2-OPT untuk TSP . ide dasarnya adalah memulai dengan solusi acak yang sesuai dengan beberapa kendala, dan kemudian mengganggunya secara lokal untuk mencari perbaikan, dengan rakus mencari perbaikan dan mengulanginya, dan mengakhiri ketika semua perbaikan lokal telah habis. kriteria desain adalah bahwa algoritma harus seefisien / menghindari penolakan sebanyak mungkin.

ada beberapa penelitian tentang algoritma gangguan [4] misalnya digunakan dalam SAGE [5] tetapi mereka tidak berorientasi pada multiset.

gangguan sederhana hanya "bertukar" dari dua posisi dalam tupel. implementasinya dalam ruby. Berikut ini adalah beberapa ikhtisar / catatan dengan referensi ke nomor baris.

qb2.rb ( gist -github)

pendekatan di sini adalah memulai dengan dua tupel deranged (# 106) dan kemudian secara lokal / rakus meningkatkan dispersi (# 107), dikombinasikan dalam konsep yang disebut derangesperse(# 97), melestarikan kekacauan. perhatikan bahwa bertukar dua posisi yang sama dalam pasangan tupel menjaga kekacauan dan dapat meningkatkan dispersi dan itu adalah (bagian dari) metode / strategi bubar.

yang derangesubroutine bekerja kiri ke kanan pada array (multiset) dan swap dengan elemen kemudian dalam array di mana swap tidak dengan unsur yang sama (# 10). Algoritma berhasil jika, tanpa swap lebih lanjut di posisi terakhir, kedua tuple masih kacau (# 16).

ada 3 pendekatan berbeda untuk merusak tupel awal. tuple ke-2 p2selalu dikocok. seseorang dapat mulai dengan tuple 1 ( p1) dipesan oleh a."urutan tertinggi kekuatan" (# 128), b.urutan acak (# 127), c.dan "urutan terendah kekuatan pertama" ("urutan terakhir kekuatan tertinggi") (# 126).

rutin dispersi disperselebih terlibat tetapi secara konsep tidak begitu sulit. lagi menggunakan swap. daripada mencoba mengoptimalkan dispersi secara umum di atas semua elemen, ia hanya mencoba untuk secara iteratif meringankan kasus terburuk saat ini. idenya adalah untuk menemukan 1 ^st elemen paling disperse, kiri ke kanan. perturbasinya adalah untuk menukar elemen kiri atau kanan ( x, yindeks) dari pasangan yang paling tidak tersebar dengan elemen lain tetapi tidak pernah ada di antara pasangan (yang akan selalu mengurangi dispersi), dan juga melewatkan upaya untuk bertukar dengan elemen yang sama ( selectdi # 71) . madalah indeks titik tengah pasangan (# 65).

namun dispersi diukur / dioptimalkan pada kedua tupel dalam pasangan (# 40) menggunakan dispersi "paling / paling kiri" di setiap pasangan (# 25, # 44).

algoritma berusaha untuk menukar elemen "terjauh" 1 ^st ( sort_by / reverse# 71).

ada dua strategi berbeda true, falseuntuk memutuskan apakah akan menukar elemen kiri atau kanan dari pasangan yang paling tidak tersebar (# 80), baik elemen kiri untuk posisi swap ke elemen kiri / kanan ke sisi kanan, atau elemen kiri atau kanan terjauh. dalam pasangan dispersi dari elemen swap.

algoritme selesai (# 91) ketika tidak dapat lagi meningkatkan dispersi (baik memindahkan lokasi dispersi terburuk ke kanan atau meningkatkan dispersi maksimum pada seluruh pasangan tupel (# 85)).

statistik adalah output untuk penolakan lebih dari c= 1000 gangguan atas 3 pendekatan (# 116) dan c= 1000 derangesperses (# 97), melihat pada 2 algoritma dispersi untuk pasangan gila dari penolakan (# 19, # 106). yang terakhir melacak dispersi rata-rata total (setelah kekacauan yang dijamin). contoh run adalah sebagai berikut

c       0.661000
b       0.824000
a       0.927000
[2.484, 2, 4]
[2.668, 2, 4]

ini menunjukkan bahwa a-truealgoritma memberikan hasil terbaik dengan ~ 92% nonrejection dan jarak disperse terburuk rata-rata ~ 2.6, dan minimum yang dijamin dari 2 lebih dari 1000 percobaan, yaitu setidaknya 1 elemen campur tangan yang tidak ada sama sekali antara semua pasangan elemen yang sama. ia menemukan solusi setinggi 3 elemen intervensi yang tidak ada bandingannya.

algoritma derangement adalah pra-penolakan waktu linier, dan algoritma dispersi (berjalan pada input gila) tampaknya mungkin ~ . $O(n \log n)$

¹ masalahnya adalah untuk menemukan pengaturan quizbowl paket yang memenuhi apa yang disebut "feng shui" [1] atau "bagus" random memesan di mana "bagus" agak subjektif dan belum "resmi" dihitung; penulis masalah telah menganalisis / menguranginya menjadi kriteria derange / dispersi berdasarkan penelitian di komunitas quizbowl dan "pakar feng shui". [2] ada ide berbeda tentang "aturan feng shui." beberapa "dipublikasikan" penelitian telah dilakukan pada algoritma tetapi muncul pada tahap awal. [3]

[1] Paket feng shui / QBWiki

[2] Paket kuis dan feng shui / Lifshitz

[3] Penempatan Pertanyaan , forum pusat sumber daya HSQuizbowl

[4] Menghasilkan Kesulitan Acak / Martinez, Panholzer, Prodinger

[5] Sage derangement algorithm (python) / McAndrew

vzn
sumber

Fyi berpikir lebih jauh, ada kesalahan dalam rutinitas derange & itu tidak selalu berubah. posisi swap dapat naik tanpa menukar apa pun. Ada perbaikan sederhana untuk menguji kesuksesan dengan benar.

vzn