DropSort rasanya panas

41

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 4dan 3keduanya 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 , jadi aturan standar berlaku!

Tuan Farquaad
sumber
Bisakah kita menghasilkan seperti [5, 4, 3, 8, 7, 6] -> [5, 8], [4,3,7,6]?
Tn. Xcoder
5
@Xcoder, baik saya tidak keberatan dengan sintaks, tetapi Anda masih harus mengurutkan daftar kedua (dan membaginya dalam hal ini). Mengetahui kapan harus berhenti adalah bagian dari tantangan;). Dan Stewie, saya tidak benar-benar tahu harus berkata apa kepada Anda. Saya melihat tantangan DropSort dan berpikir ini terdengar menyenangkan. Adakah kesempatan Anda menggunakan mesin waktu Anda untuk melompat maju dan melihat pertanyaan ini? Hanya saja jangan menggunakannya untuk melihat jawaban terbaik!
Lord Farquaad
Perhatikan bahwa menambahkan penyortiran dari sisi kiri akan menghilangkan solusi dari waktu linier.
ikegami
Haruskah {3,4,5,3,4,5,3,4,5}menghasilkan {{3,4,5,5,5},{3,4,4},{3}}?
QBrute
@Qrute saya pikir itu benar.
Lord Farquaad

Jawaban:

10

MATL , 15 10 9 byte

5 byte off menggunakan ide @beaker tentang kumulatif maksimum

t"ttY>=&)

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

1 2 5 4 3 7

kode mengambil entri pertama, kedua, ketiga dan keenam:

1 2 5     7

Kemudian proses ini diulangi pada subarray yang dibentuk oleh entri yang tersisa (dalam urutan asli):

      4 3

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.

t        % Implicit input. Duplicate
"        % Do as many times as the input size
  tt     %   Duplicate twice
  Y>     %   Cumulative maximum
  =      %   Compare for equality. Will be used as logical index
  &)     %   Two-output indexing: pushes indexed subarray, and then
         %   a subarray with the remaining entries
         % End (implicit)
         % Display stack (implicit). Empty arrays are not displayed
Luis Mendo
sumber
23

Haskell, 67 59 58 byte

(q:r)!x|x<last q=q:r!x|1<2=(q++[x]):r
_!x=[[x]]
foldl(!)[]

Penjelasan: Diberikan daftar daftar (yang sudah diurutkan) dan nilainya x, !operator akan menempatkan xpada akhir daftar pertama yang elemen terakhirnya kurang dari atau sama dengan x. Jika tidak ada daftar seperti itu, daftar [x]ditempatkan di akhir.

Cobalah online.

Cristian Lupascu
sumber
3
Ini adalah solusi yang sangat pintar. Sejujurnya saya berharap sebagian besar orang terus-menerus DropSort sampai tidak ada yang tersisa, tetapi saya berharap seseorang akan memikirkan cara yang lebih kreatif.
Lord Farquaad
13

Sekam , 10 byte

hUmü<¡Ṡ-ü<

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 ke nubBy(>)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 ü<.

hUmü<¡Ṡ-ü<  Implicit input, say x = [2,3,5,4,4,2,7].
     ¡      Iterate
      Ṡ-    list difference between argument
        ü<  and its dropsort: [[2,3,5,4,4,2,7],[4,4,2],[2],[],[],[],...
  m         Map
   ü<       dropsort: [[2,3,5,7],[4,4],[2],[],[],[],...
 U          Prefix of unique elements: [[2,3,5,7],[4,4],[2],[]]
h           Drop last element: [[2,3,5,7],[4,4],[2]]
Zgarb
sumber
10
Outgolf jawaban teratas sebesar 33% "Saya tidak tahu, rasanya kikuk"
Lord Farquaad
11

Haskell , 50 byte

import Data.List
f[]=[]
f l|r<-nubBy(>)l=r:f(l\\r)

Cobalah online!

Tidak
sumber
1
Saya hampir punya ini, hanya tidak tahu \\ fungsinya: (
H.PWiz
2
Oh itu memang fungsi yang sangat berguna! Solusi yang sangat bagus =)
flawr
7

Sekam , 16 byte

hUm₁≤¡₁>
ṠfSz⁰G▲

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.

ṠfSz⁰G▲  Helper function, takes binary function p (as ⁰) and list x (implicit).
         For example, p = (≤) and x = [2,4,3,4,5,2].
     G▲  Left scan on x with maximum: [2,4,4,4,5,5].
  Sz     Zip with x
    ⁰    using the function p: [1,1,0,1,1,0].
Ṡf       Keep elements of x at truthy indices: [2,4,4,5].

Dalam fungsi utama, kita mengulangi fungsi sisa ₁>dan menerapkan fungsi dropsort ₁≤pada hasilnya.

hUm₁≤¡₁>  Main function, implicit list argument, say x = [2,4,3,4,5,2].
     ¡    Iterate
      ₁>  the leftovers function: [[2,4,3,4,5,2],[3,2],[2],[],[],[],...
  m       Map
   ₁≤     the dropsort function: [[2,4,4,5],[3],[2],[],[],[],...
 U        Prefix of unique elements: [[2,4,4,5],[3],[2],[]]
h         Drop last element (an empty list): [[2,4,4,5],[3],[2]]
Zgarb
sumber
Sekam adalah Jelly baru ...
Erik the Outgolfer
1
@EriktheOutgolfer Dipukuli oleh MATL. : /
Zgarb
6

Python 3 , 131 112 103 95 byte

Terima kasih banyak @Mr. Xcoder untuk 19 byte yang menghancurkan !!

Terima kasih banyak @ovs untuk 17 byte yang luar biasa!

def f(x):
 a,*x=x or[0];m=[a];d=[]
 for i in x:[m,d][i<m[-1]]+=i,
 return[m]+(x and(d>[])*f(d))

Cobalah online!

Penjelasan:

def f(x):               #recursive function taking list, returns list of lists 
 if len(x)<2:return[x]  #for a single element return [element] 
 m=[x[0]];d=[]          #initialize main and dropped lists
 for i in x[1:]:[m,d][i<m[-1]]+=[i]  #append elements from the argument list accordingly into main and dropped list 
 return[m]+(d>[])*list(f(d)) #add main-list along with further evaluated dropped-list(recursived) into a list of lists
officialaimm
sumber
2
116 byte. The if-elsedapat runtuh ke [m,d][i<m[-1]]+=[i].
Tn. Xcoder
Woah, Terima kasih banyak ... Saya mencoba [m,d]hal itu tetapi tidak berhasil, entah bagaimana ....
officialaimm
1
113 byte . (len(d)>0)adalah bool(d), karena daftar kosong salah dalam Python. +1, solusi yang bagus!
Tn. Xcoder
1
95 byte
ovs
2
i,hanya kependekan dari (i,), yang merupakan tuple yang berisi a. a,*x = x or [0]adalah perpanjangan pembongkaran python3 . Berikut adalah posting SO bermanfaat tentang topik ini dengan beberapa contoh.
Ovs
6

Haskell , 113 107 102 92 byte

import Data.List
a!(b:c)|b<last a=a!c|1>0=a++[b]!c
a!b=a
g x@(b:c)|i<-[b]!c=i:g(x\\i)
g x=[]

Cobalah online!

Ini terasa sangat lama.

Penjelasan

!melakukan pengurutan drop pada daftar, sambil #mengumpulkan hiasan. gkemudian berulang kali berlaku #hingga daftar kosong merekam hasil dalam daftar.

Wisaya Gandum
sumber
1
Mengganti head adengan a!!0menghemat satu byte.
tommeding
5

APL, 27 byte

{⍵≡⍬:⍬⋄(⊂X/⍵),∇⍵/⍨~X←⍵≥⌈\⍵}

Penjelasan:

  • ⍵≡⍬:⍬: jika input kosong, kembalikan daftar kosong
  • X←⍵≥⌈\⍵: semua angka lebih besar atau sama dengan berjalan maksimum
  • (⊂X/⍵): daftar angka-angka itu,
  • ∇⍵/⍨~X: diikuti oleh hasil menjalankan fungsi ini pada angka yang tersisa
marinus
sumber
Simpan satu byte dengan {⍵≡⍬:⍬⋄(⊂⍵~r),∇r←⍵/⍨⍵<⌈\⍵}. Morten mulai khawatir dengan kurangnya respons terhadap email-emailnya. Apakah semua baik-baik saja?
Adám
Oh sayang. Saya senang di sini bahwa Anda berhasil. Sampai jumpa minggu depan.
Adám
4

JavaScript (ES6), 64 byte

f=(a,l,r=[])=>a+a&&[a.filter(e=>e<l?!r.push(e):(l=e,1)),...f(r)]

Tidak Disatukan:

f=(a,l,r=[])=>
  a+a&&                                    //any elements left?
  [a.filter(                               //filter elements that are in order,
    e=>e<l?!r.push(e):(l=e,1)              //push unsorted elements to r
   ),                                      //push() returns the new length of the array,
                                           //... so !push() will always return false
   ...f(r)                                 //recurse on r
  ]

Rick Hitchcock
sumber
1
Untuk sepersekian detik di sana saya pikir ?!ada beberapa operator baru yang mewah ...
Neil
Ha, ya, saya harus memasukkan penjelasan. Sekarang ditambahkan.
Rick Hitchcock
@Neil?!
Patrick Roberts
(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 menghapus f=kode Anda, dan mungkin kode saya mungkin memberi Anda beberapa ide tentang cara membuat golf Anda lebih banyak lagi.
David Archibald
Terima kasih, @DavidArchibald. Saya tidak dapat menghapus 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.
Rick Hitchcock
4

R , 61 byte

f=function(x)if(sum(x|1)){print(x[b<-x==cummax(x)]);f(x[!b])}

Cobalah online!

Fungsi rekursif. sum(x|1)adalah singkatan length(x), jadi rekursi ini akan berjalan sampai xkosong. cummaxmengambil maksimum kumulatif x, yang kemudian dibandingkan xlagi. Ini menghasilkan vektor boolean panjang x, di mana semua TRUE sesuai dengan nilai yang diurutkan. Kami menggunakannya untuk mengambil bagian xdan printitu. Fungsi ini kemudian dipanggil lagi pada sisa x.

JAD
sumber
4

Java 8, 182 179 177 bytes

import java.util.*;l->{List r=new Stack(),t;for(int p,i,x;l.size()>0;)for(p=l.get(0),r.add(t=new Stack()),i=0;i<l.size();p=x)if((x=l.get(i++))>=p)t.add(l.remove(--i));return r;}

-3 byte berkat @Nevay .
-2 byte dengan menggunakan Stackbukan Vector.

Penjelasan:

Coba di sini.

import java.util.*;            // Required import for List and Vector
l->{                           // Method with ArrayList<Integer> parameter and List return-type
  List r=new Stack(),          //  Return-List
       t;                      //  Temp-List
  for(int p,i,x;               //  Some temp integers
      l.size()>0;)             //  Loop (1) as long as there are still items left in the list
    for(p=l.get(0),            //   Set `p` to the first item of the list
        r.add(t=new Stack()),  //   Add a new inner List to the result-List
        i=0;i<l.size();        //   Inner loop (2) from 0 to the size of the list (exclusive)
         p=x)                  //     After every iteration, save the previous value in `p`
      if((x=l.get(i++))>=p)    //    If the current item is equal or larger than the previous:
        t.add(l.remove(--i));  //     Add it to the temp-List, and remove it from the input-List
                               //   End of inner loop (2) (implicit / single-line body)
                               //  End of loop (1) (implicit / single-line body)
  return r;                    //  Return result-List
}                              // End of method
Kevin Cruijssen
sumber
Bisakah Anda menggunakan try{}catch{}alih-alih mengecek l.size()untuk menyimpan beberapa?
TheLethalCoder
1
Anda dapat memulai loop dalam pada 0dan menghapus tanda kurung for-loop luar l->{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).
Nevay
3

C #, 188 203 byte

int[][]f(int[]a){int[]t=a.Where((n,i)=>i<1||n>=a[i-1]).ToArray(),m=a.Where((n,i)=>i>0&&n<a[i-1]).ToArray();var s=new int[][]{t}.ToList();if(m.Any())s.AddRange(f(m));return s.ToArray();}

Hitungan byte termasuk +18 untuk:

using System.Linq;

Cobalah online!

TheLethalCoder
sumber
@RickHitchcock Diperbaiki dengan biaya 15 byte! Tempat yang bagus.
TheLethalCoder
Rick Hitchcock
3

C ++ 14, 118 108 byte

Menggunakan 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 (seperti vector<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.

[](auto A,auto&R){for(auto x:A){for(auto&D:R)if(D.back()<x){D.push_back(x);goto F;}R.emplace_back(1,x);F:;}}

Cobalah online!

Tidak Disatukan:

[](auto A,auto&R){
 for(auto x:A){       //foreach item
  for(auto&D:R)       //foreach result list
   if(D.back()<x){    //x bigger than last element
    D.push_back(x);   //add x
    goto F;           //break and jump over the emplace
   }
  R.emplace_back(1,x);//create new list with this element
  F:;
 }
}
Karl Napf
sumber
Anda mungkin bisa lolos dari menghilangkan R.clear(), dan hanya meminta penelepon untuk memulai dengan wadah kosong.
Peter Cordes
@PeterCordes ide bagus, saya mungkin respec C + + jawaban saya yang lain yang ditampilkan kembali melalui parameter referensi.
Karl Napf
2

Python 2 , 88 byte

-4 byte terima kasih kepada Arnold Palmer

b,r=input(),[]
for i in b:
 for l in r:
	if l[-1]<=i:l+=[i];break
 else:r+=[[i]]
print r

Cobalah online!

Solusi serupa dengan haskell @ w0lf [jawab] [1]

Kasing yang jarang digunakan untuk for-elsekonstruksi

Iterate melalui daftar yang diurutkan for l in r(kosong di awal).
Jika elemen (dari input) ilebih besar dari elemen terakhir dari daftar l[-1], tambahkan elemen ke daftar l+=[i], hancurkan.
Jika tidak ada daftar yang diterima, tambahkan daftar baru dengan elemens inir+=[[i]]

Possum Mati
sumber
1
88 byte dengan hanya mengeluarkannya dari fungsinya.
Arnold Palmer
1

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:

z=function(x){if(length(x)){a=x[x>=cummax(x)]
append(list(a),z(x[!(x%in%a)]))}else{NULL}}

Tidak Disatukan:

z=function(x){
  if(length(x)){
    a=x[x>=cummax(x)]
    append(list(a),z(x[!(x%in%a)]))
  } else {
    NULL
  }
}
Alex Axthelm
sumber
Anda mungkin harus menghapus ini untuk saat ini sehingga Anda tidak mendapatkan downvotes saat Anda memperbaikinya.
Giuseppe
1
z=function(x)"if"(sum(x|1),{a=x[(i=x>=cummax(x))] c(list(a),z(x[!i]))},NULL)bekerja
Giuseppe
ruang antara ]dan cmerupakan baris baru (atau titik koma)
Giuseppe
Saya belum pernah melihat "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 dengan iindeks, untuk menyelesaikan %in%masalah.
Alex Axthelm
Nah, Anda sudah melakukan semua kerja keras! Saya tidak bisa menyelesaikan masalah ini sampai saya melihat implementasi Anda - saya tidak akan pernah ingat cummax!
Giuseppe
1

JavaScript (ES6), 71 70 68 byte

a=>a.map(n=>(o.find(b=>[...b].pop()<=n)||(n=[n],o)).push(n),o=[])&&o

Cukup 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 ...&&odan mengatur kembali panggilan balik map()agar menjadi lebih ringkas.

f=a=>a.map(n=>(o.find(b=>[...b].pop()<=n)||(n=[n],o)).push(n),o=[])&&o;[[1,2,5,4,3,7],[10,-1,12],[-7,-8,-5,0,-1,1],[9,8,7,6,5],[10,13,17,21],[10,10,10,9,10],[5,4,3,8,7,6],[0,2,5,4,0,7]].map(f).map(JSON.stringify).map(v=>console.log(v))
.as-console-wrapper{max-height:100%!important}

Patrick Roberts
sumber
1
&&obyte lebih pendek dari (,o).
Neil
@Neil gah! Tangkapan hebat, terima kasih
Patrick Roberts
1
Saya suka Anda [...b].pop(), tetapi saya pikir (o.find(b=>[...b].pop()<=n)||(n=[n],o)).push(n)menghemat satu atau dua byte.
Neil
Pada tingkat ini, saya akan merasa wajib untuk menandai ini sebagai pos komunitas ... sialan
Patrick Roberts
Hanya karena beberapa perubahan? Ini pada dasarnya masih kode yang sama ...
Neil
1

C (gcc) , 176 175 173 byte

#define P(x)printf("%d ",t=x);
l[2][99];t;x;i;j;w;main(a){while(scanf("%d",*l+w)>0)++w;while(i=w){P(l[a=!a][w=0])for(j=1;j<i;++j){x=l[a][j];x<t?l[!a][w++]=x:P(x)}puts("");}}

Cobalah online!

Versi yang bisa dibaca:

#define P(x)printf("%d ",t=x);
l[2][99];t;x;i;j;w;
main(a)
{
    while(scanf("%d",*l+w)>0)++w;
    while(i=w)
    {
        P(l[a=!a][w=0])
        for(j=1;j<i;++j)
        {
            x=l[a][j];
            x<t?l[!a][w++]=x:P(x)
        }
        puts("");
    }
}
Felix Palmen
sumber
175 byte .
Tn. Xcoder
Tentu saja, betapa bodohnya - terima kasih!
Felix Palmen
1

PHP, 91 103 96 85 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)

while($a){$b=$d=[];foreach($a as$i)${max($b)>$i?d:b}[]=$i;$a=$d;$r[]=$b;}print_r($r);

Input yang diberikan $a, menghasilkan hasil$r

Cantik:

while ($a) {
    $b = $d = [];
    foreach ($a as $i) {
        ${max($b) > $i ? d : b}[] = $i;
    }
    $a   = $d;
    $r[] = $b;
}

Lingkaran luar pseudo-rekursif menginisialisasi array keep $bdan discard $dmenjadi kosong, kemudian melakukan loop sortasi dasar, akhirnya mengatur discard sebagai input baru dan menambahkan keep pada hasil$r

Payung
sumber
1

PHP , 102 byte , 98 byte

<?php function s($i){static$s;foreach($i as$v)${$v<max($l)?f:l}[]=$v;$s[]=$l;!$f?:s($f);return$s;}

Cobalah online!

-4 byte, terima kasih kepada @Umbrella

Penjelasan

<?php

Fungsi mengambil daftar input sebagai array.

function s($i) {

$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.

    static $s;

Lingkari setiap nilai dalam daftar.

    foreach ($i as $v)

Apakah kurang dari anggota daftar terbesar saat ini?

        $v < max($l) ?

Ya, letakkan di daftar $funtuk penyortiran lebih lanjut.

                        $f[] = $v :

Tidak, letakkan di daftar $l.

                        $l[] = $v;

Dorong daftar $lke daftar daftar.

    $s[] = $l;

Jika ada sesuatu dalam daftar $f, kirim kembali untuk penyortiran lebih lanjut.

    !$f ?: s($f);

Kembalikan daftar daftar.

    return $s;
}
WebSmithery
sumber
1
Menghitung 31 karakter yang saya tinggalkan <?php function d($a){return$r;}, Anda dengan hati-hati menghancurkan saya. Selain itu, saya baru sadar bahwa kami berdua lupa akan hasil.
Payung
Saya telah menurunkan solusi saya untuk mencoba mengalahkan Anda tanpa menggunakan milik Anda dan saya menemukan cara Anda dapat ditingkatkan: Saya pikir Anda dapat menyimpan empat karakter dengan menggantinya $v<max($l)?$f[]=$v:$l[]=$v;dengan ${$v<max($l)?f:l}[]=$v;- setidaknya, itu berfungsi dalam pengujian saya.
Payung
@Umbrella, tidak kembali, mengeluarkan ??? Dan terima kasih untuk 4 byte itu. Saya tidak pernah berpikir untuk bekerja seperti itu, menggunakan kode untuk mengevaluasi nama variabel. Saya harus ingat untuk mempertimbangkan itu dalam tantangan di masa depan ... 🤔
WebSmithery
Ditemukan, konsensus tampaknya menerima kembali sebagai keluaran: codegolf.meta.stackexchange.com/questions/2447/…
Payung
0

Sage, 102 byte

def f(w,a=[]):
 for x in w:
  q,c=exists(a,lambda b:b[-1]<=x)
  if q:c+=[x]
  else:a+=[[x]]
 return a

Sangat mirip dengan jawaban @Dead Possum .
Menambahkan setiap anggota xdari wke daftar pertama di a{daftar daftar} dengan xlebih dari elemen terakhir itu.
jika tidak ada, tambahkan [x]ke a.

Saya akan sangat suka jika existskembali ajika tidak ada yang ditemukan! Juga mencoba menerapkan gagasan satu-jalur @ officialaimm ...

Pertanyaan: Jika saya menghapus kode saya dari fungsi, saya harus menetapkan wuntuk input kan? Jadi apakah itu akan menghemat byte?

mungkin begitu
sumber
0

Ocaml , 69 62 byte

let rec d=function h::i::t when h>i->d(h::t)|h::t->h::d t|x->x

Penjelasan:

let rec d = function (* Implicitly take an list as a parameter *)
    (* If the list starts with two elements h and i and h is greater than i, drop i and sort the list starting with h and the rest t *)
    | h::i::t when h > i -> d (h::t) 
    (* If h is not greater than i, make a new list starting with h and a tail containing the drop sorted rest *)
    | h::t -> h::d t
    (* If none of the cases apply, the list is empty. *)
    | x -> x
Palle
sumber
0

APL, 100 88 83 79 78 57 56 77 76 byte

{(E/⍵),⊂⍵/⍨~E←(⍬≢⍴)¨⍵}∘{⍵≡(S←¯1↓⍵),⊃⊃⌽⍵:⍵⋄∇S,⊃⌽⍵}{⍵≡X←⍵/⍨~V←⍵≠⌈\⍵:⍵⋄X(∇V/⍵)}

-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)

{⍵≡X←⍵/⍨~V←⍵≠⌈\⍵:⍵⋄X(∇V/⍵)} - separate the argument into nested drop-sorts
{⍵≡(S←¯1↓⍵),⊃⊃⌽⍵:⍵⋄∇S,⊃⌽⍵}  - un-nesting (passed the result of the above)
{(E/⍵),⊂⍵/⍨~E←(⍬≢⍴)¨⍵}∘     - fixing array mishaps (passed the result of the above)
Zacharý
sumber
{⍬≢⍴⍵}dapat menjadi(⍬≢⍴)
Kritixi Lithos
Sudah melakukannya tanpa melihat komentar Anda,
Zacharý
Apa tujuannya {(⍵/⍨~E),⊂⍵/⍨E←(⍬≡⍴)¨⍵}? Tampaknya dipisahkan dari yang lain
Kritixi Lithos
Tanpa itu, test case pertama akan menjadi seperti [[1,2,5,7],[4],3], bukan yang diperlukan [[1,2,5,7],[4],[3]].
Zacharý
Anda mungkin dapat mempersingkat dfn itu menjadi hanya(,¨)
Kritixi Lithos
0

Jelly, 26 byte

<»\¬x@ðW;µ⁸Ñ
<»\x@µÑ
1Ŀ¹L?

Ini adalah metode yang sama dengan jawaban APL marinus.

Cobalah online! .

Zacharý
sumber
0

JavaScript (Node.js) , 125 109 106 byte

- 16 18 byte dari Zacharý

-1 dengan menghapus {dan }dengan mengubah incrementer untuk memasukkan "setel terakhir ke saat ini"

m=x=>{z=[[],[]];l=NaN;for(i=0;i<x.length;l=x[i++])if(l>x[i])z[1].push(x[i]);else z[0].push(x[i]);return z}

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 NaNakan selalu menghasilkan false. Menarik!

Penjelasan:

m = x => {                         // Create function
  z = [[], []];                      // Initialize dropsort output
  l = NaN;                           // Initialize last element
  for (i = 0; i < x.length; l=x[i++])// For each item in input...
    if (l > x[i])                    // If current item is greater than previous
      z[1].push(x[i]);               // Then add it to the first part of output
    else                             // Elsewise
      z[0].push(x[i]);               // Add it to the nonordered part of the dropsort
                                     // Set last item to current item
  }                                  // Repeat
  return z                           // Return finished dropsort
}                                    // End function

Cobalah online!

Stan Strum
sumber
Apakah Anda harus menggunakan var?
Zacharý
@ Zacharý, biarkan aku periksa!
Stan Strum
Paren tidak diperlukan di sekitar x.
Zacharý