Ini adalah tantangan operasi paling sedikit di mana tujuannya adalah untuk mengurutkan vektor ke dalam urutan naik menggunakan pembalikan paling sedikit. Algoritme Anda hanya dapat mengurutkan vektor menggunakan "pembalikan sub-vektor" 1 , tetapi dapat menggunakan operasi lain untuk operasi aritmatika, loop, memeriksa apakah itu diurutkan dll . Jumlah pembalikan sub-vektor yang dilakukan algoritma Anda adalah nilainya.
1 A "pembalikan sub-vektor":
- Pilih rentang angka dalam vektor, dan balikkan elemen dalam rentang itu.
Untuk memberikan contoh sederhana, jika Anda mulai dengan vektor {4,3,2,1}
, maka Anda dapat mengurutkannya dalam banyak cara berbeda:
- Balikkan seluruh vektor. Ini jelas merupakan pendekatan terpendek karena hanya membutuhkan satu pembalikan:
{4,3,2,1} -> {1,2,3,4}
- Anda dapat melakukan versi semacam gelembung, yang membutuhkan 6 pembalikan:
{4,3,2,1} -> {3,4,2,1} -> {3,2,4,1} -> {2,3,4,1} -> {2,3,1,4} -> {2,1,3,4} -> {1,2,3,4}
- Anda bisa mulai dengan 3 elemen pertama, lalu tiga terakhir, dan akhirnya dua pertama dan dua terakhir, yang membutuhkan 4 swap:
{4,3,2,1} -> {2,3,4,1} -> {2,1,4,3} -> {1,2,4,3} -> {1,2,3,4}
- ... dan seterusnya. Ada banyak pilihan yang tidak terbatas (Anda dapat mengulangi operasi apa pun jika Anda mau).
Aturan dan persyaratan:
Kode Anda harus selesai dalam waktu kurang dari satu menit untuk daftar dengan 100 angka. Anda dapat mengatur waktu ini sendiri, tapi tolong mainkan 2 .
Anda harus menyimpan indeks awal dan akhir dari semua swap yang Anda lakukan, sehingga solusinya dapat diverifikasi. (Saya akan menjelaskan apa artinya ini di bawah).
Kode harus bersifat deterministik.
Anda dapat mengambil input pada format apa pun yang Anda inginkan: Vektor numerik, daftar terkait, array dengan panjang ... apa pun yang Anda suka.
Anda dapat melakukan apa pun yang Anda suka pada salinan vektor. Itu termasuk mencoba pembalikan yang berbeda dan memeriksa mana yang paling efisien. Brute-forcing baik-baik saja, tetapi tetap pada batas waktu.
Skor adalah jumlah total flips untuk 5 vektor uji. Tie-breaker akan mencantumkan stempel tanggal.
Contoh:
4 1 23 21 49 2 7 9 2 | Vektor / daftar awal 4 1 2 9 7 2 49 21 23 | (2, 8) (membalik elemen antara indeks 2 dan 8) 4 1 2 2 7 9 49 21 23 | (3, 5) 4 1 2 2 7 9 23 21 49 | (6, 8) 4 1 2 2 7 9 21 23 49 | (6, 7) 2 2 1 4 7 9 21 23 49 | (0, 3) 1 2 2 4 7 9 21 23 49 | (0, 2)
Skor akan menjadi 6, karena Anda melakukan 6 pembalikan. Anda harus menyimpan (tidak mencetak) indeks yang tercantum di sebelah kanan pada format yang sesuai yang dapat dengan mudah dicetak / dikeluarkan untuk keperluan verifikasi.
Vektor uji:
133, 319, 80, 70, 194, 333, 65, 21, 345, 142, 82, 491, 92, 167, 281, 386, 48, 101, 394, 130, 111, 139, 214, 337, 180, 24, 443, 35, 376, 13, 166, 59, 452, 429, 406, 256, 133, 435, 446, 304, 350, 364, 447, 471, 236, 177, 317, 342, 294, 146, 280, 32, 135, 399, 78, 251, 467, 305, 366, 309, 162, 473, 27, 67, 305, 497, 112, 399, 103, 178, 386, 343, 33, 134, 480, 147, 466, 244, 370, 140, 227, 292, 28, 357, 156, 367, 157, 60, 214, 280, 153, 445, 301, 108, 77, 404, 496, 3, 226, 37
468, 494, 294, 42, 19, 23, 201, 47, 165, 118, 414, 371, 163, 430, 295, 333, 147, 336, 403, 490, 370, 128, 261, 91, 173, 339, 40, 54, 331, 236, 255, 33, 237, 272, 193, 91, 232, 452, 79, 435, 160, 328, 47, 179, 162, 239, 315, 73, 160, 266, 83, 451, 317, 255, 491, 70, 18, 275, 339, 298, 117, 145, 17, 178, 232, 59, 109, 271, 301, 437, 63, 103, 130, 15, 265, 281, 365, 444, 180, 257, 99, 248, 378, 158, 210, 466, 404, 263, 29, 117, 417, 357, 44, 495, 303, 428, 146, 215, 164, 99
132, 167, 361, 145, 36, 56, 343, 330, 14, 412, 345, 263, 306, 462, 101, 453, 364, 389, 432, 32, 200, 76, 268, 291, 35, 13, 448, 188, 11, 235, 184, 439, 175, 159, 360, 46, 193, 440, 334, 128, 346, 192, 263, 466, 175, 407, 340, 393, 231, 472, 122, 254, 451, 485, 257, 67, 200, 135, 132, 421, 205, 398, 251, 286, 292, 488, 480, 56, 284, 484, 157, 264, 459, 6, 289, 311, 116, 138, 92, 21, 307, 172, 352, 199, 55, 38, 427, 214, 233, 404, 330, 105, 223, 495, 334, 169, 168, 444, 268, 248
367, 334, 296, 59, 18, 193, 118, 10, 276, 180, 242, 115, 233, 40, 225, 244, 147, 439, 297, 115, 354, 248, 89, 423, 47, 458, 64, 33, 463, 142, 5, 13, 89, 282, 186, 12, 70, 289, 385, 289, 274, 136, 39, 424, 174, 186, 489, 73, 296, 39, 445, 308, 451, 384, 451, 446, 282, 419, 479, 220, 35, 419, 161, 14, 42, 321, 202, 30, 32, 162, 444, 215, 218, 102, 140, 473, 500, 480, 402, 1, 1, 79, 50, 54, 111, 189, 147, 352, 61, 460, 196, 77, 315, 304, 385, 275, 65, 145, 434, 39
311, 202, 126, 494, 321, 330, 290, 28, 400, 84, 6, 160, 432, 308, 469, 459, 80, 48, 292, 229, 191, 240, 491, 231, 286, 413, 170, 486, 59, 54, 36, 334, 135, 39, 393, 201, 127, 95, 456, 497, 429, 139, 81, 293, 359, 477, 404, 129, 129, 297, 298, 495, 424, 446, 57, 296, 10, 269, 350, 337, 39, 386, 142, 327, 22, 352, 421, 32, 171, 452, 2, 484, 337, 359, 444, 246, 174, 23, 115, 102, 427, 439, 71, 478, 89, 225, 7, 118, 453, 350, 109, 277, 338, 474, 405, 380, 256, 228, 277, 3
Saya cukup yakin bahwa menemukan solusi optimal adalah NP-hard (karena penyortiran panekuk adalah).
2 Ya, orang-orang dengan komputer yang sangat cepat mungkin mendapat manfaat, karena batas waktu satu menit. Setelah banyak diskusi saya pikir itu yang terbaik jika semua orang melakukan benchmarking sendiri, itu bukan tantangan kode tercepat.
sumber
n-1
flips? Saya hanya bisa membuktikan batas bawah sekitar 50.Jawaban:
Java, algoritma genetika, 80 + 81 + 79 + 78 + 80 = 398 (sebelumnya
418)Setelah mencoba banyak ide yang berbeda dan kebanyakan gagal, saya menentukan algoritma ini: mulai dengan array input, coba semua kemungkinan pembalikan dan pertahankan sejumlah hasil dengan jumlah run terkecil, kemudian lakukan hal yang sama untuk hasil tersebut, hingga kami mendapatkan array yang diurutkan.
Dengan "berjalan" yang saya maksud subarrays maksimal yang muncul tepat atau terbalik dalam array yang diurutkan. Pada dasarnya mereka adalah sub-susunan yang diurutkan maksimal, tetapi jika elemen berulang, jumlah elemen di tengah harus cocok. Misal jika array yang diurutkan
2, 2, 3, 3, 4, 4
kemudian4, 3, 3, 2
dijalankan tetapi2, 2, 3, 4
tidak (dan tidak juga2, 3, 2
).Dalam versi ini saya mengoptimalkan algoritme untuk membalikkan hanya pada batas run dan hanya jika run terbalik dapat bergabung dengan run yang baru berdekatan. Juga, menjalankan disesuaikan dan bergabung pada setiap langkah, untuk menghindari menghitung ulang mereka dari array yang dimodifikasi. Ini memungkinkan saya untuk meningkatkan "ukuran populasi" dari 30 menjadi sekitar 3000, dan menjalankan beberapa simulasi pada berbagai ukuran.
Input adalah daftar angka yang dipisahkan oleh koma dan / atau spasi (dari stdin). Jika input kosong, program menjalankan 5 tes. Masing-masing membutuhkan sekitar 40 detik di sini.
sumber
Satu gerakan brute-force kemudian pemilihan sortir (juga solusi naif), 90 + 89 + 88 + 87 + 89 = 443 gerakan
untuk setiap langkah pertama yang mungkin, cobalah, lalu lakukan semacam seleksi.
Ya, ini adalah solusi naif lainnya.
Saya tidak yakin ini harus menjadi edit atau posting lain, tetapi tampaknya solusinya terlalu sederhana, jadi pengeditan dipilih.
Sortir Pilihan (Solusi Naif), 92 + 93 + 95 + 93 + 96 = 469 gerakan
Solusi naif menggunakan semacam seleksi.
Ada HARUS ada beberapa solusi yang lebih baik, tapi posting ini karena saya tidak menemukan yang lebih baik (tanpa pencarian brute-force).
(Kode di atas adalah JavaScript Shell )
sumber