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.
Jawaban:
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.n n - c ( π) c ( π) π π σ SEBUAH B n - c ( σ- 1∘ π)
sumber
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.saya j= 1 saya j ∥ M.( s ) - M( s′) ∥2 d( s , s′)
Perbarui: silakan lihat komentar Oleksandr
sumber