Jumlah minimum transposisi untuk mengurutkan daftar

15

Dalam mencoba menyusun algoritma penyortiran saya sendiri, saya mencari patokan optimal yang dapat saya bandingkan. Untuk pengurutan elemen A yang tidak disortir dan pengurutan B yang terurut , apa cara yang efisien untuk menghitung jumlah transposisi optimal untuk mendapatkan dari A ke B ?

Transposisi didefinisikan sebagai perpindahan posisi 2 elemen dalam daftar, jadi misalnya

1 2 4 3

memiliki satu transposisi (transposisi 4 dan 3) untuk membuatnya

1 2 3 4

Sesuatu seperti

1 7 2 5 9 6

membutuhkan 4 transposisi (7, 2), (7, 6), (6,5), (9, 7)

Pembaruan (9/7/11): pertanyaan diubah untuk menggunakan "transposisi" alih-alih "swap" untuk merujuk ke pertukaran yang tidak berdekatan.

sova
sumber
bagaimana jika Anda bisa bertukar tetangga saja? bagaimana saya bisa mengetahui jumlah minimum swap?

Jawaban:

23

Jika Anda hanya berurusan dengan permutasi dari unsur, maka Anda akan perlu persis n - c ( π ) swap, dimana c ( π ) adalah jumlah siklus dalam dekomposisi siklus menguraikan dari π . Karena jarak ini bi-invariant, mentransformasikan π menjadi σ (atau A menjadi B , atau sebaliknya) membutuhkan n - c ( σ - 1π ) yang bergerak.nn-c(π)c(π)ππσSEBUAHBn-c(σ-1π)

Anthony Labarre
sumber
Meskipun sudah memilih sejak lama, itu baru saja diklik hari ini. Seperti kubus Rubik, kan: D?
sova
11

Jarak swap juga dapat tertanam secara isometrik dalam ruang Euclidean. Untuk setiap string, buat sebuah matriks mana M i j = 1 jika saya muncul sebelum j dan nol jika tidak. Maka jarak Frobenius M ( s ) - M ( s ) 2 adalah jarak swap d ( s , s ) . (dari slide Graham Cormode ). Tidak seanggun jawaban Anthony, tetapi cukup mudah untuk dihitung.M.(s)M.sayaj=1sayajM.(s)-M.(s)2d(s,s)

Perbarui: silakan lihat komentar Oleksandr

Suresh Venkat
sumber
SEBUAH2SEBUAHF
walaupun jika semua yang ingin Anda lakukan adalah menghitung perbedaan, maka kuadrat dari norma frobenius seharusnya bekerja dengan benar?
Suresh Venkat
yang tentu saja jarak Hamming untuk matriks 0-1
Suresh Venkat
2
Oleksandr: Jadi saya kira Anda menafsirkan "swapping" sebagai "bertukar dua elemen yang berdekatan"?
Anthony Labarre