Apakah ada algoritme yang efisien untuk menemukan dearrangement ke-i?

9

Inilah latar belakang untuk pertanyaan ini. Teman-teman dan saya sedang bermain permainan di mana semua orang perlu memberi orang lain hadiah. Untuk menentukan siapa yang harus memberikan hadiah kepada siapa, kami memutuskan untuk menggambar banyak. Tapi masalahnya adalah, seseorang mungkin akhirnya memberikan hadiah sendiri, yang tidak lucu. Anda dapat melihat bahwa jumlah yang diharapkan dari orang yang tidak beruntung tersebut adalah 1, jadi ini cukup sering terjadi.

Untuk tujuan ini, dearrangement tampaknya sangat cocok. Jika saya dapat dengan adil menghasilkan suatu perjanjian sayang, maka saya dapat memilih satu perjanjian sayang dan menggunakannya untuk memutuskan siapa yang memberikan hadiah kepada siapa.

Generasi sayang acak dapat dilakukan dengan metode Las Vegas. Tetapi masalahnya adalah, hanya diharapkan waktu berjalan polinomial. Jadi saya sampai pada masalah ini untuk menemukan kesesuaian saya. Jika saya dapat secara acak memilih i di [1, D_n], dan menggunakan beberapa algoritma waktu polinomial waktu (efisien) terburuk untuk mendapatkan persetujuan kedua, maka hal itu dilakukan.

permutations Santa Zhang
sumber
1
Bisakah Anda jelaskan motivasi untuk pertanyaan itu? yaitu mengapa Anda tertarik dengan pertanyaan ini?
Kaveh
2
Mungkin Anda ingin bermain santa rahasia dan tidak mau mengambil risiko :)
Lev Reyzin
Bisakah Anda menambahkan baris tentang apa yang Anda maksud dengan dearrangement?
Vijay D

Jawaban:

9

Sebenarnya ini mungkin pertanyaan yang bagus tetapi dirumuskan dengan buruk dalam bentuknya saat ini. Algoritma yang terkenal untuk menghasilkan kekacauan acak memiliki waktu linier yang diharapkan, tapi mungkin itu masalah terbuka untuk menemukan algoritma waktu polinomial kasus terburuk.

Lihat misalnya: http://www.siam.org/proceedings/analco/2008/anl08_022martinezc.pdf (dan slide: http://www.lsi.upc.edu/~conrado/research/talks/analco08.pdf )

Didest
sumber
Ini sepertinya jawaban yang tepat untuk saya.
Suresh Venkat
10
Bukankah pengulangan! N ​​= (n − 1) (! (N − 1) +! (N − 2)) yang dijelaskan dalam en.wikipedia.org/wiki/Derangement langsung mengarah pada algoritma polinomial terburuk untuk acak generasi?
David Eppstein
Ya kamu benar. Saya berpikir ada tangkapan kecil karena Anda harus dapat menghasilkan angka acak dalam himpunan bagian sewenang-wenang dari {1, ..., n} dalam polytime kasus terburuk, tetapi itu mudah dilakukan.
didest
0

Mengapa tidak, untuk setiap posisi i , pilih secara acak dari semua elemen selain saya ? Misalnya, Anda bisa memilih indeks ke dalam array asli dari [0..n-2] , dan jika Anda mendapatkan j> = i Anda menggunakan j +1 .

menepuk
sumber
3
Apakah itu membuat semua kekacauan sama mungkin?
David Eppstein
oh, titik bagus - ini akan menempatkan elemen nanti dalam array secara istimewa sebelumnya dalam array. Jika Anda mengisi slot di array target dalam urutan acak semua kekacauan maka kemungkinan akan sama (berdasarkan simetri).
tepuk