Masalah menarik saat menyortir

14

Diberi tabung dengan bola bernomor (acak). Tabung memiliki lubang untuk mengeluarkan bola. Pertimbangkan langkah-langkah berikut untuk satu operasi:

  1. Anda dapat memilih satu atau lebih bola dari lubang dan ingat urutan pengambilan bola tersebut.
  2. Anda perlu memiringkan pipa ke sisi kiri sehingga bola yang tersisa di pipa bergeser ke kiri dan menempati ruang kosong yang dibuat dengan menghapus bola.
  3. Anda tidak seharusnya mengubah urutan pengambilan bola bernomor dari pipa. Sekarang Anda menempatkan mereka kembali di pipa menggunakan ruang kosong yang diciptakan oleh gerakan bola.

Langkah 1 hingga 3 dianggap sebagai satu operasi.

Cari tahu operasi minimum yang diperlukan untuk mengurutkan bola bernomor dalam urutan menaik.

Misalnya: Jika tabung berisi:[1 4 2 3 5 6]

Kemudian kita bisa mengeluarkan dan dan , dan jika kita memiringkan pipa ke kiri, kita dapatkan [ 1 2 3 ] , dan kita masukkan ( 4 5 6 ) agar ke ujung pipa untuk mendapatkan .5 6456[1 2 3](4 5 6)[1 2 3 4 5 6]

Jadi jumlah minimum langkah yang diperlukan adalah 1. Saya perlu menemukan operasi minimum untuk menyortir pipa.

Adakah ide atau petunjuk tentang cara mengatasi masalah ini?

rakesh
sumber
Jika mereka datang dalam urutan terbalik, Anda harus mengeluarkan 2, 3, ... dalam rangka dan menambahkan pada akhirnya, untuk operasi dalam semua. Ini jelas merupakan kasus terburuk. n
vonbrand
2
8,7,6,5,4,3,2,1 -> 75318642 -> 51627384 -> 12345678 dengan selalu mengeluarkan posisi aneh.
adrianN
Meringkas jawaban saya: jumlah minimum operasi yang diperlukan untuk mengurutkan permutasi adalah log 2 ( d ( π - 1 ) + 1 ) , di mana d ( ) adalah jumlah keturunan. πlog2(d(π1)+1)d()
Yuval Filmus
Saya suka memikirkannya dalam hal menghilangkan inversi. Dengan setiap operasi, Anda dapat menghapus inversi antara set dan S - X (di mana S adalah seluruh set bola). Jadi, Anda hanya harus memilih set X Anda dengan hati-hati. XSXSX
Joe

Jawaban:

10

Tentukan nomor run-partisi dari permutasi , dilambangkan r ( π ) , menggunakan proses berikut. Biarkan k menjadi bilangan bulat maksimal sehingga angka min ( π ) , ... , k muncul dalam urutan yang meningkat dalam π . Hapus dari π , dan ulangi prosesnya. Jumlah putaran yang dibutuhkan untuk mengkonsumsi seluruh permutasi adalah r ( π ) .πr(π)kmin(π),,kππr(π)

Sebagai contoh, mari kita hitung . Kami pertama-tama menyisihkan 1 , untuk mendapatkan 6273584 . Lalu kami menyisihkan 234 , untuk mendapatkan 6758 . Lalu kami menyisihkan 5 , untuk mendapatkan 678 . Akhirnya, kami menyisihkan 678 untuk mendapatkan permutasi kosong. Ini membutuhkan empat putaran, jadi r ( 62735814 ) = 4 .r(62735814)1627358423467585678678r(62735814)=4

Bagaimana representasi ini berguna untuk menyortir ? Ambil setiap menjalankan kedua, yaitu 234 , 678 , dan pindahkan angka-angka ini ke kanan untuk mendapatkan 51627384 (edit: dalam urutan mereka muncul dalam permutasi, yaitu 627384 ). Sekarang hanya ada dua run, yaitu 1234 , 5678 , dan kita dapat mengurutkan daftar dengan memindahkan 5678 ke kanan.62735814234,678516273846273841234,56785678

Sekarang izinkan saya membuat dugaan berikut: Untuk permutasi , biarkan Π adalah himpunan semua permutasi yang dapat dijangkau dari π dalam satu gerakan. Kemudian min α Π r ( α ) = r ( π ) / 2 .πΠπminαΠr(α)=r(π)/2

Dengan dugaan ini, mudah untuk menunjukkan bahwa jumlah minimal gerakan yang diperlukan untuk mengurutkan permutasi adalah log 2 r ( π ) , dan saya telah memverifikasi rumus ini untuk semua permutasi dalam S n untuk n 8 .πlog2r(π)Snn8

Sunting: Berikut adalah interpretasi berbeda dari nomor run-partisi yang memberikan algoritma waktu linier untuk menghitungnya, dan memungkinkan saya untuk membuat sketsa bukti dugaan saya, sehingga memverifikasi rumus .log2r(π)

Pertimbangkan permutasi lagi. Alasan bahwa proses pertama berakhir pada 1 adalah bahwa 2 muncul sebelum 1 . Demikian pula, putaran kedua berakhir pada 4 karena 5 muncul sebelum 4 , dan seterusnya. Oleh karena itu jumlah run-partisi dari permutasi adalah jumlah i s sehingga saya + 1 muncul sebelum i .62735814121454ii+1i

Kita dapat menyatakan ini dengan lebih ringkas jika kita melihat kebalikan dari permutasi. Pertimbangkan lagi . Ambil π - 1 = 72485136 . Permutasi ini memiliki tiga keturunan: 7 2 48 5 1 36 (keturunan adalah posisi yang lebih kecil dari yang sebelumnya). Masing-masing keturunan sesuai dengan awal menjalankan baru. Jadi r ( π ) sama dengan satu ditambah jumlah keturunan pada π - 1 .π=62735814π1=7248513672485136r(π)π1

Seperti apa operasi itu dalam hal ? biarkan B menjadi himpunan angka yang kita pindah ke kanan, dan A menjadi himpunan angka yang tetap di kiri. Kami mengganti angka dalam A dengan permutasi pada { 1 , , | A | } mewakili urutan relatif mereka, dan ganti angka dalam B dengan permutasi pada { | A | + 1 , ... , | A | + | B | }π1BAA{1,,|A|}B{|A|+1,,|A|+|B|}. Misalnya, perhatikan langkah . Dalam hal permutasi terbalik, itu adalah 7 248 5 1362 468 1 357 . Jadi 75 dipetakan ke 21 dan 248136 dipetakan ke 468357 .627358145162738472485136246813577521248136468357

Sebuah keturunan di π - 1 hilang setelah operasi hanya jika x A dan y B . Sebaliknya, dalam hal π - 1 , partisi menjadi A dan B berhubungan dengan A -runs dan B -runs; setiap kali B- run berakhir dan A- run dimulai, ada keturunan. Untuk "membunuh" keturunan, kita harus beralih dari A- run ke Bxyπ1xAyBπ1ABABBAAB-Lari. Jika kita membunuh dua keturunan, kita akan beralih di tengah dari run ke A- run, menimbulkan keturunan.BA

Argumen ini dapat diformalkan untuk menunjukkan bahwa jika muncul dari π melalui operasi, maka d ( α - 1 ) d ( π - 1 ) / 2 , di mana d ( ) adalah jumlah keturunan. Ini setara dengan r ( α ) r ( π ) / 2 απd(α1)d(π1)/2d()r(α)r(π)/2, dengan demikian membuktikan satu arah dugaan saya. Arah lainnya lebih mudah, dan sudah diuraikan di atas: kita cukup menjalankan setiap detik dan mendorongnya ke kanan untuk mendapatkan permutasi memuaskan r ( α ) = r ( π / 2 ) .αr(α)=r(π/2)

Yuval Filmus
sumber
Anda mengambil beberapa putaran bola sekaligus, saya mengerti itu tidak diperbolehkan.
vonbrand
1
Saya mengambil mereka dalam urutan mereka muncul dalam permutasi . Itu legal.
Yuval Filmus
saya agak bingung. dapatkah Anda jelaskan jumlah operasi minimum yang diperlukan untuk menyortir [6 5 4 3 2 1] dan Anda juga menyebutkan seperti "Ambil setiap putaran kedua, yaitu 234.678, dan pindahkan angka-angka ini ke kanan untuk mendapatkan 51627384" bisakah Anda jelaskan ini dengan detail dan juga bagaimana cara menghitung r (π) secara efisien?
user6709
1) , jadi Anda akan membutuhkan 3 operasi. Misalnya, 654321 531 | 642 51 | 6234 1234 | 56 . r(654321)=6654321531|64251|62341234|56
Yuval Filmus
2) Anda mengambil semua angka yang dimiliki run ini (dalam urutan yang muncul dalam permutasi), dan memindahkannya ke kanan. Dalam hal ini, Anda mengambil dan memindahkannya ke kanan, meninggalkan 51 ke kiri. 62738451
Yuval Filmus