Partisi ke dalam peningkatan urutan

16

Spesifikasi

Tantangan ini sederhana untuk dinyatakan: input Anda adalah array non-kosong dari integer non-negatif, dan tugas Anda adalah mempartisi menjadi sesedikit mungkin peningkatan berikutnya. Lebih formal lagi, jika array input adalah A, maka output adalah array array Bsehingga:

  • Setiap array dalam Bbentuk partisi Amenjadi disjoint (tidak harus berdekatan). Secara induktif, ini berarti bahwa baik Barray singleton yang mengandung A, atau elemen pertama Badalah Aurutan dan sisanya membentuk partisi Adengan urutan berikutnya dihapus.
  • Setiap array dalam B(tidak harus sepenuhnya) meningkat.
  • Jumlah array di Bminimal.

Baik input dan output dapat diambil dalam format array asli bahasa Anda. Perhatikan bahwa mungkin ada beberapa output yang benar.

Contoh

Pertimbangkan array input A = [1,2,1,2,5,4,7,1]. Satu kemungkinan keluaran adalah B = [[1],[1,2,4,7],[1,2,5]]. Kondisi partisi terbukti dari diagram ini:

A    1 2 1 2 5 4 7 1
B[0]               1
B[1] 1 2       4 7
B[2]     1 2 5

Juga, setiap array Bmeningkat. Akhirnya, Atidak dapat dibagi menjadi dua urutan yang meningkat, jadi panjangnya Bjuga minimal. Jadi ini adalah output yang valid.

Aturan dan penilaian

Anda dapat menulis fungsi atau program lengkap. Hitungan byte terendah menang, dan celah standar tidak diizinkan. Tidak ada batasan waktu, tetapi Anda harus mengevakuasi solusi Anda pada semua kasus uji sebelum mengirimkannya.

Uji kasus

Hanya satu output yang mungkin ditampilkan, tetapi mungkin ada beberapa opsi yang valid. Secara khusus, urutan array dalam hasil tidak masalah (tetapi masing-masing array harus dalam urutan yang meningkat).

[0] -> [[0]]
[3,5,8] -> [[3,5,8]]
[2,2,2,2] -> [[2,2,2,2]]
[1154,1012,976,845] -> [[845],[976],[1012],[1154]]
[6,32,1,2,34,8] -> [[1,2,8],[6,32,34]]
[1,12,1,12,1,13] -> [[1,1,1,13],[12,12]]
[6,4,6,13,18,0,3] -> [[0,3],[4,6,13,18],[6]]
[1,2,3,2,3,4,7,1] -> [[1,1],[2,2,3,4,7],[3]]
[0,9,2,7,4,5,6,3,8] -> [[0,2,3,8],[4,5,6],[7],[9]]
[7,1,17,15,17,2,15,1,6] -> [[1,1,6],[2,15],[7,15,17],[17]]
[4,12,2,10,15,2,2,19,16,12] -> [[2,2,2,12],[4,10,15,16],[12,19]]
[10,13,9,2,11,1,10,17,19,1] -> [[1,1],[2,10,17,19],[9,11],[10,13]]
[3,7,3,8,14,16,19,15,16,2] -> [[2],[3,3,8,14,15,16],[7,16,19]]
[15,5,13,13,15,9,4,2,2,17] -> [[2,2,17],[4],[5,9],[13,13,15],[15]]
Zgarb
sumber
3
Aturan tampaknya memungkinkan solusi seperti [0,5,2,0] -> [[0,5],[0,2]](yaitu, mendaur ulang nol pertama alih-alih menggunakan masing-masing satu kali). Apakah itu disengaja?
feersum
@feersum Itu tidak disengaja, tangkapan yang bagus. Saya sudah menulis ulang kondisinya B, semoga sekarang lebih jelas.
Zgarb

Jawaban:

3

Haskell, 54 byte

n#[]=[[n]]
n#(l:c)|[n]<=l=(n:l):c|1<2=l:n#c
foldr(#)[]

Contoh penggunaan: foldr(#)[] [4,12,2,10,15,2,2,19,16,12]->[[2,2,2,12],[4,10,15,16],[12,19]]

Cara kerjanya: buka daftar input mulai dari ujung kanan. Membangun daftar keluaran (daftar) dengan mengawali elemen saat nuntuk sublist pertama ldi mana nkurang atau sama dengan kepala l. Jika tidak ada, buat daftar singleton baru ndi akhir daftar output.

nimi
sumber
1

Pyth, 20 byte

fTu&ahfSI+THGHGQm[)Q

Cobalah online: Demonstrasi atau Test Suite

Pendekatan serakah. Saya membuat len(input)daftar kosong. Kemudian saya mengulangi setiap nomor dalam daftar inputpilih yang pertama, yang masih diurutkan setelah menambahkan nomor.

Penjelasan:

fTu&ahfSI+THGHGQm[)Q   implicit: Q = input list
                m[)Q   create a list of empty lists and assign to G
  u            Q       iterate over all numbers H in input:
      f     G             filter for lists T in G, which satisfy:
         +TH                 create a new list out of T and H
       SI                    and check if it is sorted
     h                    take the first such list T
    a        H            and append H
   &          G           logical and with G (so that u doesn't overwrite G)
fT                     remove all empty lists
Jakube
sumber
@ThomasKwa Telah menguji cukup banyak test case tambahan sekarang. Tidak dapat menemukan satu pun, yang memberikan hasil yang salah. Saya cukup yakin, bahwa Greedy selalu mengembalikan hasil yang benar.
Jakube
@ThomasKwa Oh, tandingan itu adalah untuk strategi serakah yang berbeda (menemukan berikutnya meningkat terpanjang, menghapusnya dan berulang). Saya juga sepertinya tidak dapat menemukan test case yang gagal untuk pengajuan ini ...
Zgarb
Yah, saya pikir beban ada pada penjawab untuk membuktikan itu bekerja. Saya akan angkat suara jika ini terbukti valid.
lirtosiast