Seperti yang dijelaskan dalam pertanyaan ini :
Dropsort, dirancang oleh David Morgan-Mar, adalah contoh dari "algoritma penyortiran" waktu-linear yang menghasilkan daftar yang, pada kenyataannya, diurutkan, tetapi hanya berisi beberapa elemen asli. Elemen apa pun yang tidak paling tidak sebesar maksimum elemen sebelumnya hanya dihapus dari daftar dan dibuang.
Untuk menggunakan salah satu dari kasus uji mereka, input dari {1, 2, 5, 4, 3, 7}
hasil {1, 2, 5, 7}
, karena 4
dan 3
keduanya dijatuhkan karena lebih kecil dari nilai "diurutkan" sebelumnya 5
,.
Kami tidak ingin algoritma "pengurutan", kami ingin mereka menjadi yang sebenarnya. Oleh karena itu, saya ingin Anda menulis sebuah program yang, mengingat daftar angka, mengeluarkan daftar daftar DropSorted (untuk menjadi algoritma penyortiran lengkap, kita perlu menggabungkan daftar ini, tetapi menggabungkan dua daftar yang diurutkan telah dilakukan sebelumnya, dan meminta Anda melakukannya lagi cukup banyak mengajukan dua pertanyaan, jadi pertanyaan ini secara khusus merupakan langkah "pemecahan" dari DropSort lengkap kami).
Pengaturan dan konten daftar kami sangat penting. Output dari program Anda harus setara dengan output DropSort, diikuti oleh DropSort dari nilai yang dibuang, dan seterusnya hingga Anda hanya memiliki daftar rantai yang diurutkan. Sekali lagi, meminjam suite tes yang ada (dan menambahkan dua lagi):
Input -> Output
{1, 2, 5, 4, 3, 7} -> {{1, 2, 5, 7}, {4}, {3}}
{10, -1, 12} -> {{10, 12}, {-1}}
{-7, -8, -5, 0, -1, 1} -> {{-7, -5, 0, 1}, {-8, -1}}
{9, 8, 7, 6, 5} -> {{9}, {8}, {7}, {6}, {5}}
{10, 13, 17, 21} -> {{10, 13, 17, 21}}
{10, 10, 10, 9, 10} -> {{10, 10, 10, 10}, {9}} //Note equivalent values aren't dropped
{5, 4, 3, 8, 7, 6} -> {{5, 8}, {4, 7}, {3, 6}}
{0, 2, 5, 4, 0, 7} -> {{0, 2, 5, 7}, {4}, {0}}
Anda dapat menganggap input tidak kosong.
Ini kode-golf , jadi aturan standar berlaku!
[5, 4, 3, 8, 7, 6] -> [5, 8], [4,3,7,6]
?{3,4,5,3,4,5,3,4,5}
menghasilkan{{3,4,5,5,5},{3,4,4},{3}}
?Jawaban:
MATL ,
15109 byte5 byte off menggunakan ide @beaker tentang kumulatif maksimum
Input adalah vektor baris numerik, dalam format
[1, 2, 5, 4, 3, 7]
(koma adalah opsional). Outputnya berisi daftar yang dipisahkan oleh baris baru, dengan angka di setiap daftar dipisahkan oleh spasi.Cobalah online! Atau verifikasi semua kasus uji .
Penjelasan
Diberikan array, kode mengambil dari setiap entri yang sama dengan maksimum kumulatif hingga entri itu.
Misalnya diberikan
kode mengambil entri pertama, kedua, ketiga dan keenam:
Kemudian proses ini diulangi pada subarray yang dibentuk oleh entri yang tersisa (dalam urutan asli):
Ini perlu dilakukan sampai subarray dari entri yang tersisa kosong. Batas atas pada jumlah iterasi yang diperlukan adalah ukuran input. Iterasi terakhir mungkin tidak diperlukan. Dalam hal ini mereka beroperasi pada array kosong, menghasilkan array kosong tambahan.
Pada akhirnya, tumpukan berisi array yang diperlukan dan mungkin beberapa array kosong, yang tidak ditampilkan sama sekali.
sumber
Haskell,
67 5958 bytePenjelasan: Diberikan daftar daftar (yang sudah diurutkan) dan nilainya
x
,!
operator akan menempatkanx
pada akhir daftar pertama yang elemen terakhirnya kurang dari atau sama denganx
. Jika tidak ada daftar seperti itu, daftar[x]
ditempatkan di akhir.Cobalah online.
sumber
Sekam , 10 byte
Cobalah online!
Ini adalah kombinasi dari jawaban Husk saya yang lain dan jawaban Haskell dari xnor . Duplikatnya
ü<
terasa kikuk, tapi saya tidak tahu bagaimana cara menghilangkannya ...Penjelasan
Fungsi
ü<
diterjemahkan kenubBy(>)
dalam Haskell. Itu melintasi daftar dari kiri ke kanan, menjaga elemen-elemen yang tidak ada elemen sebelumnya disimpan lebih besar. Dengan kata lain, ia melakukan tetes. Elemen sisa diperoleh dengan mengambil perbedaan daftar dari daftar asli dan hasilü<
.sumber
Haskell , 50 byte
Cobalah online!
sumber
\\
fungsinya: (Sekam , 16 byte
Cobalah online!
Penjelasan
Baris pertama ini adalah fungsi utama, dan yang kedua adalah fungsi pembantu tingkat tinggi (dibutuhkan fungsi sebagai argumen dan mengembalikan fungsi baru). Itu diakses oleh subskrip
₁
. Idenya adalah yang₁≤
melakukan droport dan₁>
memberikan elemen sisa.Dalam fungsi utama, kita mengulangi fungsi sisa
₁>
dan menerapkan fungsi dropsort₁≤
pada hasilnya.sumber
Python 3 ,
131 112 10395 byteTerima kasih banyak @Mr. Xcoder untuk 19 byte yang menghancurkan !!
Terima kasih banyak @ovs untuk 17 byte yang luar biasa!
Cobalah online!
Penjelasan:
sumber
if-else
dapat runtuh ke[m,d][i<m[-1]]+=[i]
.[m,d]
hal itu tetapi tidak berhasil, entah bagaimana ....(len(d)>0)
adalahbool(d)
, karena daftar kosong salah dalam Python. +1, solusi yang bagus!i,
hanya kependekan dari(i,)
, yang merupakan tuple yang berisia
.a,*x = x or [0]
adalah perpanjangan pembongkaran python3 . Berikut adalah posting SO bermanfaat tentang topik ini dengan beberapa contoh.Haskell ,
11310710292 byteCobalah online!
Ini terasa sangat lama.
Penjelasan
!
melakukan pengurutan drop pada daftar, sambil#
mengumpulkan hiasan.g
kemudian berulang kali berlaku#
hingga daftar kosong merekam hasil dalam daftar.sumber
head a
dengana!!0
menghemat satu byte.APL, 27 byte
Penjelasan:
⍵≡⍬:⍬
: jika input kosong, kembalikan daftar kosongX←⍵≥⌈\⍵
: semua angka lebih besar atau sama dengan berjalan maksimum(⊂X/⍵)
: daftar angka-angka itu,∇⍵/⍨~X
: diikuti oleh hasil menjalankan fungsi ini pada angka yang tersisasumber
{⍵≡⍬:⍬⋄(⊂⍵~r),∇r←⍵/⍨⍵<⌈\⍵}
. Morten mulai khawatir dengan kurangnya respons terhadap email-emailnya. Apakah semua baik-baik saja?JavaScript (ES6), 64 byte
Tidak Disatukan:
Tampilkan cuplikan kode
sumber
?!
ada beberapa operator baru yang mewah ...?!
(i,n,o=[])=>[i.filter(a=>(n||a)<=a?(n=a,1):!o.push([a])),...o]
Rupanya, pikiran yang hebat berpikir (agak) sama. Sayangnya saya tidak bisa mengurangi byte lagi ... Hanya dengan mencatat, Anda dapat menghapusf=
kode Anda, dan mungkin kode saya mungkin memberi Anda beberapa ide tentang cara membuat golf Anda lebih banyak lagi.f=
dari kode saya, karena ini bersifat rekursif. Milik Anda adalah pendekatan yang menarik, tetapi tampaknya tidak berhasil untuk beberapa kasus uji. Misalnya, ia kembali[[5,8],[4],[3],[7],[6]]
untuk kasus berikutnya-terakhir.R , 61 byte
Cobalah online!
Fungsi rekursif.
sum(x|1)
adalah singkatanlength(x)
, jadi rekursi ini akan berjalan sampaix
kosong.cummax
mengambil maksimum kumulatifx
, yang kemudian dibandingkanx
lagi. Ini menghasilkan vektor boolean panjangx
, di mana semua TRUE sesuai dengan nilai yang diurutkan. Kami menggunakannya untuk mengambil bagianx
danprint
itu. Fungsi ini kemudian dipanggil lagi pada sisax
.sumber
Java 8,
182179177 bytes-3 byte berkat @Nevay .
-2 byte dengan menggunakan
Stack
bukanVector
.Penjelasan:
Coba di sini.
sumber
try{}catch{}
alih-alih mengecekl.size()
untuk menyimpan beberapa?0
dan menghapus tanda kurung for-loop luarl->{List r=new Vector(),t;for(int p,i,x;l.size()>0;)for(p=l.get(0),r.add(t=new Vector()),i=0;i<l.size();p=x)if((x=l.get(i++))>=p)t.add(l.remove(--i));return r;}
(-3 byte).C #,
188203 byteHitungan byte termasuk +18 untuk:
Cobalah online!
sumber
C ++ 14,
118108 byteMenggunakan algoritma dari jawaban Haskell w0lf .
Sebagai lambda generik yang tidak disebutkan namanya. Parameter pertama adalah sebuah wadah dari nilai-nilai untuk dropsort (seperti
vector<int>
) dan parameter kedua membutuhkan wadah kosong yang kompatibel (sepertivector<vector<int>>
) untuk nilai pengembalian melalui referensi.Di versi pertama program, ada
R.clear;()
pernyataan pertama, sehingga wadah kontainer tidak perlu kosong. Peter Cordes berpikir ini bisa menjadi spesifikasi, jadi menjatuhkan 10 byte untuk itu.Cobalah online!
Tidak Disatukan:
sumber
R.clear()
, dan hanya meminta penelepon untuk memulai dengan wadah kosong.Python 2 , 88 byte
-4 byte terima kasih kepada Arnold Palmer
Cobalah online!
Solusi serupa dengan haskell @ w0lf [jawab] [1]
Kasing yang jarang digunakan untuk
for-else
konstruksiIterate melalui daftar yang diurutkan
for l in r
(kosong di awal).Jika elemen (dari input)
i
lebih besar dari elemen terakhir dari daftarl[-1]
, tambahkan elemen ke daftarl+=[i]
, hancurkan.Jika tidak ada daftar yang diterima, tambahkan daftar baru dengan elemens ini
r+=[[i]]
sumber
R, Bekerja dalam proses (89, tetapi gagal)
Memegang beberapa pekerjaan di sini, karena saya memundurkan diri ke sudut menggunakan
%in%
(Gagal pada entri duplikat, khususnya kasus uji terakhir), dan saya perlu melakukan hal-hal lain sekarang, tapi ini di sini jika ada yang ingin membangun di atasnya:Tidak Disatukan:
sumber
z=function(x)"if"(sum(x|1),{a=x[(i=x>=cummax(x))] c(list(a),z(x[!i]))},NULL)
bekerja]
danc
merupakan baris baru (atau titik koma)"if"
sebelumnya, tapi saya cukup baru dalam bermain golf. Anda harus memposting sebagai jawaban Anda sendiri, dan saya dapat mencatatnya. Saya suka apa yang Anda lakukan dengani
indeks, untuk menyelesaikan%in%
masalah.cummax
!JavaScript (ES6),
717068 byteCukup sederhana, hanya mengulangi array, mencari array dalam pertama yang nilai terakhirnya adalah
<=
nilai berikutnya untuk dijatuhkan, jika tidak ada, tambahkan array dalam baru dengan nilai berikutnya ke output, jika tidak tambahkan nilai berikutnya ke yang pertama menemukan array dalam yang sesuai dengan kondisi.Pembaruan
Berkat Neil, tersimpan tiga byte yang dikonversi
(...,o)
menjadi...&&o
dan mengatur kembali panggilan balikmap()
agar menjadi lebih ringkas.sumber
&&o
byte lebih pendek dari(,o)
.[...b].pop()
, tetapi saya pikir(o.find(b=>[...b].pop()<=n)||(n=[n],o)).push(n)
menghemat satu atau dua byte.Japt , 29 byte
Uji secara online!
sumber
C (gcc) ,
176175173 byteCobalah online!
Versi yang bisa dibaca:
sumber
PHP,
911039685 byte(Diedit untuk menambahkan 12 karakter
print_r($r);
untuk memenuhi persyaratan ke output)(Diedit untuk menghapus 7 byte ketika memungkinkan Kesalahan PHP)
(Diedit untuk menghapus 11 byte saat memindah tugas golf lebih lanjut)
Input yang diberikan
$a
, menghasilkan hasil$r
Cantik:
Lingkaran luar pseudo-rekursif menginisialisasi array keep
$b
dan discard$d
menjadi kosong, kemudian melakukan loop sortasi dasar, akhirnya mengatur discard sebagai input baru dan menambahkan keep pada hasil$r
sumber
PHP ,
102 byte, 98 byteCobalah online!
-4 byte, terima kasih kepada @Umbrella
Penjelasan
Fungsi mengambil daftar input sebagai array.
$s
, yang akan menjadi daftar daftar yang akhirnya dikembalikan, dinyatakan statis. Ini memperluas cakupannya ke semua panggilan fungsi ini, yang memungkinkan fungsi dipanggil secara rekursif tanpa harus meneruskan daftar hasil ini sebagai argumen atau mengembalikannya.Lingkari setiap nilai dalam daftar.
Apakah kurang dari anggota daftar terbesar saat ini?
Ya, letakkan di daftar
$f
untuk penyortiran lebih lanjut.Tidak, letakkan di daftar
$l
.Dorong daftar
$l
ke daftar daftar.Jika ada sesuatu dalam daftar
$f
, kirim kembali untuk penyortiran lebih lanjut.Kembalikan daftar daftar.
sumber
<?php function d($a){return$r;}
, Anda dengan hati-hati menghancurkan saya. Selain itu, saya baru sadar bahwa kami berdua lupa akan hasil.$v<max($l)?$f[]=$v:$l[]=$v;
dengan${$v<max($l)?f:l}[]=$v;
- setidaknya, itu berfungsi dalam pengujian saya.Sage, 102 byte
Sangat mirip dengan jawaban @Dead Possum .
Menambahkan setiap anggota
x
dariw
ke daftar pertama dia
{daftar daftar} denganx
lebih dari elemen terakhir itu.jika tidak ada, tambahkan
[x]
kea
.Saya akan sangat suka jika
exists
kembalia
jika tidak ada yang ditemukan! Juga mencoba menerapkan gagasan satu-jalur @ officialaimm ...Pertanyaan: Jika saya menghapus kode saya dari fungsi, saya harus menetapkan
w
untuk input kan? Jadi apakah itu akan menghemat byte?sumber
Ocaml ,
6962 bytePenjelasan:
sumber
APL,
1008883797857567776 byte-0 byte terima kasih kepada Kritixi Lithos ...
Cobalah online!
Pasti ada cara yang lebih baik untuk melakukan ini ( Ada ). Setiap tips sangat dihargai dan disambut.
Bagaimana?
(Catatan, beberapa penjelasan ini mungkin salah, karena saya lupa cara kerjanya)
sumber
{⍬≢⍴⍵}
dapat menjadi(⍬≢⍴)
{(⍵/⍨~E),⊂⍵/⍨E←(⍬≡⍴)¨⍵}
? Tampaknya dipisahkan dari yang lain[[1,2,5,7],[4],3]
, bukan yang diperlukan[[1,2,5,7],[4],[3]]
.(,¨)
Jelly, 26 byte
Ini adalah metode yang sama dengan jawaban APL marinus.
Cobalah online! .
sumber
JavaScript (Node.js) ,
125109106 byte-
1618 byte dari Zacharý-1 dengan menghapus
{
dan}
dengan mengubah incrementer untuk memasukkan "setel terakhir ke saat ini"Pada dasarnya, bertanya adalah item saat ini lebih besar dari item terakhir, tambahkan ke daftar pertama. Jika tidak, tambahkan yang kedua.
Ditemukan selama ini bahwa membandingkan nomor apa pun
NaN
akan selalu menghasilkanfalse
. Menarik!Penjelasan:
Cobalah online!
sumber
var
?x
.