Algoritma untuk mengurutkan pasangan angka

14

Saya sudah menanyakan pertanyaan ini di stackoverflow , tapi mungkin lebih cocok untuk situs ini.

Masalahnya adalah:

Saya memiliki N pasang bilangan bulat yang tidak ditandatangani. Saya perlu menyortirnya. Vektor akhir dari pasangan harus diurutkan secara tidak menurun dengan angka pertama di setiap pasangan dan tidak meningkat dengan yang kedua di setiap pasangan. Setiap pasangan dapat mengganti elemen pertama dan kedua di titik mana pun. Terkadang tidak ada solusi, jadi saya harus membuang pengecualian.

Contoh:

in pairs:
1 5
7 1
3 8
5 6

out pairs:
1 7     <-- swapped
1 5     
6 5     <-- swapped
8 3     <-- swapped

^^ Tanpa bertukar pasangan tidak mungkin untuk membangun solusinya. Jadi kami menukar pasangan (7, 1), (3, 8) dan (5, 6) dan membangun hasilnya. atau

in pairs:
1 5
6 9

out:
not possible

Terima kasih

edit:

Tom Sirgedas on SO mengusulkan solusi terbaik . Sangat mudah untuk diimplementasikan dan bekerja di O (log (n) * n). Terima kasih atas jawaban dan minatnya. Saya sangat menikmati analisis mjqxxxx.

Klark
sumber
6
Masalah menarik. Tanpa bertukar itu langsung, tetapi dengan bertukar itu tidak jelas bahwa ada solusi unik.
Dave Clarke
2
Solusi unik tidak selalu ada. Yaitu (1, 10), (5, 6). Keduanya (1, 10), (5, 6) dan (1, 10), (6, 5) benar.
Klark
4
Lain kali harap sertakan tautan. stackoverflow.com/questions/5323941/…
Tsuyoshi Ito
2
Salah satu teman saya mendapatkannya sebagai pertanyaan wawancara tes-kertas. Jadi saya rasa itu hanya karena penasaran :)
Klark
3
(1) Klark, Terima kasih atas jawabannya. (2) Saya tidak berpikir bahwa pertanyaan ini adalah pertanyaan tingkat penelitian, tetapi saya kira itu adalah ruang lingkup yang harus diubah. Saya memulai diskusi tentang meta .
Tsuyoshi Ito

Jawaban:

8

Katakanlah bahwa dua pasang dan p 2 = ( a 2 , b 2 ) yang tidak-swap kompatibel jika mereka dapat ditempatkan dalam rangka baik dalam daftar diurutkan tanpa swapping salah satu. Ini benar jika salah satu ( a 1a 2b 1b 2 ) atau ( a 2a 1b 2bp1=(a1,b1)p2=(a2,b2)(a1a2b1b2) . Perhatikan bahwa p 1 dan p 2 ada-swap kompatibel jika dan hanya jika merekadua-swap kompatibel(karena urutan parsial memenuhi didefinisikan p 1p 2p * 2p * 1 , di mana * menunjukkan operasi swap) . Akhirnya, p 1 dan p 2 adalahsalah satu-swap kompatibeljika mereka dapat ditempatkan dalam rangka baik dalam daftar diurutkan dengan tepat satu dari mereka bertukar. Ini benar jika p 1 dan(a2a1b2b1)p1p2p1p2p2p1p1p2p1 tidak kompatibel dengan swap Dalam kasus yang tersisa, p 1 dan p 2 sama sekali tidak kompatibel: mereka tidak dapat memenuhi kondisi pesanan terlepas dari keadaan swap mereka.p2p1p2

Masalahnya sekarang dapat dipecahkan sebagai berikut. Uji setiap pasang pasangan. Jika ada pasangan yang tidak kompatibel, tidak ada solusi, dan kami bisa melempar pengecualian. Kalau tidak, perhatikan grafik dengan node yang sesuai dengan pasangan asli, dan tepi antara pasangan node yang tidak kompatibel satu-swap. Setiap pasangan node harus memiliki status swap yang sama dalam daftar yang diurutkan dengan benar, dan oleh karena itu semua node di setiap komponen yang terhubung dari grafik harus memiliki status swap yang sama. Kita perlu menentukan apakah status swap seluruh komponen ini dapat ditetapkan secara konsisten. Uji semua pasangan node dalam setiap komponen yang terhubung. Jika ada pasangan yang tidak kompatibel dengan swap, tidak ada solusi, dan kami dapat memberikan pengecualian. Sekarang uji semua pasangan komponen yang terhubung (yaitu, untuk komponen C1dan , uji semua pasangan node p 1C 1 dan p 2C 2 ). Kita tahu bahwa setiap pasangan komponen setidaknya satu-swap yang kompatibel, tetapi beberapa pasangan mungkin juga tidak-swap yang kompatibel (karena setiap pasangan node yang tidak terhubung dengan tepi setidaknya satu-swap yang kompatibel, dan mungkin juga tidak ada- swap kompatibel). Pertimbangkan grafik tereduksi dengan node yang sesuai dengan komponen yang terhubung, dan tepi antara dua node jika komponen yang sesuai tidak kompatibel dengan swap. Ada solusi untuk masalah awal jika dan hanya jika grafik ini 2 -warna. Jika tidak ada 2C2p1C1p2C222-warna, tidak ada solusi, dan kita bisa melempar pengecualian. Jika ada, maka tukar semua node di semua komponen dalam satu warna. Kami sekarang dijamin bahwa dua node mana pun tidak kompatibel dengan swap, sehingga kami dapat mengurutkan daftar pasangan menggunakan urutan parsial yang ditentukan.

Setiap langkah dalam algoritma, dan karenanya seluruh algoritma, dapat dilakukan dalam waktu .O(N2)


UPDATE: Konstruksi yang jauh lebih elegan adalah sebagai berikut. Jika sepasang pasangan tidak kompatibel dengan swap, sambungkan node yang sesuai dengan tepi (memaksa mereka untuk menjadi warna yang berbeda dalam 2 warna). Jika sepasang pasangan tidak kompatibel satu-swap, sambungkan node yang sesuai dengan rantai panjang 2 (memaksa mereka menjadi warna yang sama dalam setiap 2-pewarnaan). Ada solusi jika dan hanya jika grafik yang dihasilkan 2-colorable. Untuk membuat solusi dari pewarnaan grafik biru-merah, tukar pasangan-pasangan yang simpulnya berwarna biru, lalu urutkan daftar yang dihasilkan.

mjqxxxx
sumber
1
Terima kasih banyak atas jawabannya. Saya sangat menikmati membacanya. Periksa jawaban yang diajukan pada SO. Meskipun tidak mengandalkan teori grafik yang berarti kurang menarik daripada solusi elegan Anda :), ini lebih cepat. Terima kasih atas waktu Anda.
Klark
3

Misalkan X (a, b) menunjukkan variabel biner yang menunjukkan apakah pasangan (a, b) harus ditukar. Pertimbangkan pasangan berpasangan yang berbeda (a, b) dan (c, d) dan tulis batasan biner pada variabel X (a, b) dan X (c, d) yang dipenuhi jika dan hanya jika kedua pasangan berada dalam urutan yang benar setelah melakukan swap yang ditunjukkan oleh X (a, b) dan X (c, d), masing-masing. Gabungan dari semua batasan biner tersebut adalah rumus 2-SAT dalam n variabel dan klausa O (n ^ 2) yang memuaskan jika dan hanya jika masalah asli memiliki solusi. Ini dapat diperiksa dalam waktu O (n ^ 2).


Adapun solusi asli, hanya perhatikan bahwa semua kendala adalah dari bentuk X (a, b) = X (c, d) atau X (a, b)! = X (c, d) (atau X (a, b) = konstan), jadi algoritma sederhana "gabungkan dan periksa bipartiteness" berfungsi:

Mulailah dengan masing-masing X menjadi perwakilan untuk set yang hanya berisi dirinya sendiri; kemudian untuk setiap pasangan (X, Y) sedemikian rupa sehingga X = Y adalah kendala, gabungkan komponen-komponen yang dimiliki X dan Y; dan akhirnya memeriksa bahwa grafik yang dikontrak, di mana setiap komponen adalah satu simpul dan beberapa sisi bergabung dengan komponen yang mengandung X dan Y jika hubungan X! = Y harus dipegang, adalah bipartit.

David
sumber
1
X(Sebuah,b)=X(c,d)
Begitu? Relasi ekivalensi di sini adalah penutupan transitif relasi (a, b) R (c, d) jika a <c dan b> d atau sebaliknya. Mungkin saya tidak sepenuhnya eksplisit, tetapi ini harus jelas dari jawaban saya.
david
1
a<cb>dX(a,b)X(c,d)(1,10)(2,5)(3,7)
1
XYX¬Y
1
Apa Anda sedang bercanda? Pertama-tama, hubungan apa pun antara hanya dua variabel dapat dinyatakan sebagai rumus 2-SAT. Misalnya, X = Y sama dengan (X menyiratkan Y) dan (bukan X menyiratkan bukan Y). Di sisi lain, jika semua kendala memang dari bentuk X = Y atau X = bukan Y, maka tidak perlu menjalankan algoritma 2SAT sama sekali: algoritma "menggabungkan dan memeriksa bipartiteness" yang lebih sederhana yang saya jelaskan bekerja sebelumnya.
david