Mencari ruang permutasi

Saya diberikan n objek, dan satu set n permutasi dari n objek ini (dari n! Total permutasi). Ada permutasi mendasar yang sebenarnya, yang saya tahu adalah salah satu di antara set permutasi, tetapi saya tidak tahu yang mana. Namun oracle tahu permutasi yang sebenarnya. Untuk menemukan permutasi yang sebenarnya, saya diizinkan untuk menanyakan oracle untuk perbandingan berpasangan antara 2 objek (apakah b sebelum dalam permutasi benar?).

Strategi naif adalah melakukan pencarian biner (tanyakan pertanyaan perbandingan berpasangan "benar" yang menghilangkan setengah permutasi pada setiap tahap), untuk menemukan permutasi yang benar dalam langkah-langkah log n. Pertanyaan saya adalah, bisakah ini selalu dilakukan? Atau bisakah saya menemukan permutasi permusuhan yang permusuhan sehingga O (log n) tidak cukup.

Sunting:
Contoh: Katakan benda saya 1,2,3,4. Set permutasi adalah {1243, 2341, 1342, 3412}. Saya tidak tahu permutasi yang sebenarnya. Saya bertanya "Apakah 2 sebelum 4 dalam permutasi yang benar?". Sang oracle mengembalikan ya. Jadi saya tahu itu di antara dua permutasi pertama. Saya kemudian bertanya "Apakah 1 sebelum 3 dalam permutasi yang benar?" untuk menemukan permutasi yang sebenarnya.

complexity-theory lower-bounds search-problem permutations elexhobby
sumber

1) Oracle mengimplementasikan relasi pemesanan lengkap? 2) Saya menganggap permutasi "benar" adalah minimum atau maksimum dari hubungan itu? 3) Sebelum Anda dapat mencari biner Anda harus mengurutkan. 4) Menemukan resp minimum. maksimum dimungkinkan dalam waktu linier. 5) Mengingat bahwa set input tidak berurutan, Anda tidak dapat melarikan diri memeriksa setiap permutasi input setidaknya sekali, sehingga batas bawah linier sepele. 6) Itu semua mengasumsikan bahwa Anda tidak tahu apa-apa tentang hubungan pesanan; jika Anda tahu sesuatu, Anda mungkin dapat memanfaatkannya.

Raphael

@ Raphael: Pertanyaan saya tidak jelas seperti yang saya tulis sebelumnya. Lihat apakah contoh yang saya tambahkan membantu. Saya khawatir dengan jumlah pertanyaan yang harus Anda tanyakan pada oracle.

elexhobby

Jika saya memahami masalahnya, maka saya pikir set ini tidak dapat dipotong setengah dengan pasangan tunggal 213456 124356 123465 132456 124356 123546.

Louis

pertanyaan yang menarik adalah subset permutasi apa yang akan diikat dengan log?

Nikos M.

Pertimbangkan rangkaian perintah berikut , yang saya berikan untuk : Semoga generalisasi ke sewenang-wenang jelas. $n$ $n = 6$

123456 213456 132456 124356 123546 123465

$123456 \\ 213456 \\ 132456 \\ 124356 \\ 123546 \\ 123465$

n

$n$

Jika Anda tidak pernah membandingkan dan maka Anda tidak dapat membedakan permutasi dari permutasi . Ini berarti bahwa Anda memerlukan setidaknya perbandingan (ini bukan argumen, tetapi dapat dikonversi menjadi satu); ini ketat (untuk contoh ini). $i$ $i+1$ $1$ $i+1$ $n-1$

Izinkan saya juga menyebutkan dua makalah terkenal di daerah:

Fredman menunjukkan bahwa jika ada banyak kemungkinan pemesanan , maka Anda dapat menemukan yang benar menggunakan . $\Gamma$ $\log_2 \Gamma + 2n$
Kahn dan Kim menunjukkan bahwa jika pemesanan potensial merupakan semua pemesanan yang mungkin memperpanjang beberapa pesanan parsial, maka kueri sudah cukup. $O(\log \Gamma)$

Yuval Filmus
sumber

Mencari ruang permutasi

Jawaban: