Wie in dieser Frage beschrieben :
Dropsort, entworfen von David Morgan-Mar, ist ein Beispiel für einen linearen "Sortieralgorithmus", der eine Liste erzeugt, die zwar sortiert ist, aber nur einige der ursprünglichen Elemente enthält. Jedes Element, das nicht mindestens so groß ist wie das Maximum der vorhergehenden Elemente, wird einfach aus der Liste entfernt und verworfen.
Zu einem ihrer Testfällen verwendet werden , eine Eingabe von {1, 2, 5, 4, 3, 7}
Ausbeuten {1, 2, 5, 7}
, wie 4
und 3
sind sowohl für fiel kleiner ist als die zuvor „sortiert“ -Wert 5
.
Wir wollen keine "Sortier" -Algorithmen, wir wollen, dass sie die Realität sind. Daher möchte ich, dass Sie ein Programm schreiben, das anhand einer Liste von Zahlen eine Liste von DropSorted-Listen ausgibt (um einen vollständigen Sortieralgorithmus zu erhalten, müssten diese Listen zusammengeführt werden, aber das Zusammenführen von zwei sortierten Listen wurde zuvor durchgeführt Wenn Sie aufgefordert werden, es erneut zu tun, werden zwei Fragen gestellt, und diese Frage ist speziell der "Aufteilungsschritt" unseres vollständigen DropSort.
Die Anordnung und der Inhalt unserer Listen sind jedoch von entscheidender Bedeutung. Die Ausgabe Ihres Programms muss der Ausgabe einer DropSort-Datei entsprechen, gefolgt von einer DropSort-Datei mit den verworfenen Werten usw., bis Sie nur noch eine Liste sortierter Ketten haben. Ausleihen der vorhandenen Testsuite (und Hinzufügen von zwei weiteren):
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}}
Sie können davon ausgehen, dass die Eingabe nicht leer ist.
Dies ist Code-Golf , daher gelten die Standardregeln!
[5, 4, 3, 8, 7, 6] -> [5, 8], [4,3,7,6]
?{3,4,5,3,4,5,3,4,5}
ergeben{{3,4,5,5,5},{3,4,4},{3}}
?Antworten:
MATL ,
15109 Bytes5 Bytes weniger , wenn die Idee des kumulativen Maximums von @beaker verwendet wird
Die Eingabe ist ein numerischer Zeilenvektor im Format
[1, 2, 5, 4, 3, 7]
(Kommas sind optional). Die Ausgabe enthält durch Zeilenumbrüche getrennte Listen, wobei die Nummern in jeder Liste durch Leerzeichen getrennt sind.Probieren Sie es online! Oder überprüfen Sie alle Testfälle .
Erläuterung
Bei einem gegebenen Array wählt der Code jeden Eintrag aus, der dem kumulativen Maximum bis zu diesem Eintrag entspricht.
Zum Beispiel gegeben
Der Code wählt den ersten, zweiten, dritten und sechsten Eintrag aus:
Anschließend wird der Vorgang in dem aus den verbleibenden Einträgen gebildeten Unterfeld wiederholt (in der ursprünglichen Reihenfolge):
Dies muss durchgeführt werden, bis das Subarray der verbleibenden Einträge leer ist. Eine Obergrenze für die erforderliche Anzahl von Iterationen ist die Eingabegröße. Die letzten Iterationen sind möglicherweise nicht erforderlich. In diesem Fall bearbeiten sie ein leeres Array und erzeugen zusätzliche leere Arrays.
Am Ende enthält der Stapel die erforderlichen Arrays und möglicherweise mehrere leere Arrays, die überhaupt nicht angezeigt werden.
quelle
Haskell,
67 5958 BytesErläuterung: Bei einer gegebenen Liste von Listen (die bereits sortiert sind) und einem Wert
x
wird der!
Operatorx
am Ende der ersten Liste platziert, deren letztes Element kleiner oder gleich istx
. Wenn keine solche Liste vorhanden ist, wird die Liste[x]
am Ende platziert.Probieren Sie es online aus.
quelle
Schale , 10 Bytes
Probieren Sie es online!
Dies ist eine Kombination aus meiner anderen Husk-Antwort und der Haskell-Antwort von xnor . Das Duplikat
ü<
fühlt sich klobig an, aber ich weiß nicht, wie ich es loswerden soll ...Erläuterung
Die Funktion
ü<
übersetztnubBy(>)
in Haskell. Es durchläuft eine Liste von links nach rechts, wobei die Elemente beibehalten werden, für die kein zuvor beibehaltenes Element streng größer ist. Mit anderen Worten, es wird eine Dropssortierung durchgeführt. Die verbleibenden Elemente werden erhalten, indem die Listendifferenz der ursprünglichen Liste und das Ergebnis von genommen werdenü<
.quelle
Haskell , 50 Bytes
Probieren Sie es online!
quelle
\\
Funktion: (Schale , 16 Bytes
Probieren Sie es online!
Erläuterung
Diese erste Zeile ist die Hauptfunktion und die zweite ist eine Hilfsfunktion höherer Ordnung (sie nimmt eine Funktion als Argument und gibt eine neue Funktion zurück). Es wird durch den Index zugegriffen
₁
. Die Idee ist, dass₁≤
Dropsort ausgeführt wird und₁>
die verbleibenden Elemente ausgegeben werden.In der Hauptfunktion iterieren wir
₁>
die Restfunktion und wenden die Dropssort-Funktion₁≤
auf die Ergebnisse an.quelle
Python 3 ,
131 112 10395 BytesVielen Dank @Mr. Xcoder für unglaubliche 19 Bytes !!
Vielen Dank an @ovs für unglaubliche 17 Bytes!
Probieren Sie es online!
Erläuterung:
quelle
if-else
kann zusammengeklappt werden[m,d][i<m[-1]]+=[i]
.[m,d]
Ding ausprobiert, aber es hat irgendwie nicht funktioniert ...(len(d)>0)
istbool(d)
, weil leere Listen in Python falsch sind. +1, nette Lösung!i,
ist nur eine Abkürzung für(i,)
, die ein Tupel enthälta
.a,*x = x or [0]
ist das erweiterte Entpacken von python3 . Hier ist ein hilfreicher SO-Beitrag zu diesem Thema mit einigen Beispielen.Haskell ,
11310710292 BytesProbieren Sie es online!
Das fühlt sich wirklich lang an.
Erläuterung
!
Führt die Drop-Sortierung für eine Liste durch, während#
die Schnitte gesammelt werden.g
wird dann wiederholt angewendet,#
bis die Liste leer ist, und die Ergebnisse in einer Liste aufgezeichnet.quelle
head a
durch wirda!!0
ein Byte gespeichert.APL, 27 Bytes
Erläuterung:
⍵≡⍬:⍬
: Wenn die Eingabe leer ist, geben Sie die leere Liste zurückX←⍵≥⌈\⍵
: Alle Zahlen größer oder gleich dem laufenden Maximum(⊂X/⍵)
: die Liste dieser Nummern,∇⍵/⍨~X
: gefolgt vom Ergebnis der Ausführung dieser Funktion für die verbleibenden Nummernquelle
{⍵≡⍬:⍬⋄(⊂⍵~r),∇r←⍵/⍨⍵<⌈\⍵}
. Morten macht sich Sorgen, dass er nicht auf seine E-Mails reagiert. Ist alles in Ordnung?JavaScript (ES6), 64 Byte
Ungolfed:
Code-Snippet anzeigen
quelle
?!
?!
(i,n,o=[])=>[i.filter(a=>(n||a)<=a?(n=a,1):!o.push([a])),...o]
Anscheinend denken große Köpfe ähnlich. Leider kann ich keine Bytes mehr abschneiden ... Nur zur Erinnerung, Sie könnenf=
Ihren Code entfernen , und vielleicht gibt Ihnen mein Code einige Ideen, wie Sie Ihren noch weiter verbessern können.f=
meinen Code nicht entfernen , da er rekursiv ist. Ihr Ansatz ist interessant, scheint aber in einigen Testfällen nicht zu funktionieren. Beispielsweise wird[[5,8],[4],[3],[7],[6]]
für den vorletzten Fall zurückgegeben.R , 61 Bytes
Probieren Sie es online!
Rekursive Funktion.
sum(x|1)
ist eine Abkürzung fürlength(x)
, daher wird diese Rekursion ausgeführt, bis siex
leer ist.cummax
nimmt das kumulative Maximum vonx
, das dann wieder verglichenx
wird. Dies erzeugt einen booleschen Längenvektorx
, bei dem alle TRUEs sortierten Werten entsprechen. Wir verwenden das, um eine Teilmenge vonx
und zu nehmenprint
. Im Übrigen wird die Funktion dann erneut aufgerufenx
.quelle
Java 8,
182179177 Bytes-3 Bytes dank @Nevay .
-2 Bytes mit
Stack
anstelle vonVector
.Erläuterung:
Probieren Sie es hier aus.
quelle
try{}catch{}
anstatt zu prüfen, gegenl.size()
einige zu speichern?0
und die Klammern der äußeren for-Schleife entfernenl->{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 Bytes).C #,
188203 BytesDie Byteanzahl umfasst +18 für:
Probieren Sie es online!
quelle
C ++ 14,
118108 BytesVerwenden des Algorithmus aus der Haskell-Antwort von w0lf .
Wie unbenanntes generisches Lambda. Der erste Parameter ist ein Container mit den zu löschenden Werten (like
vector<int>
) und der zweite Parameter erfordert einen kompatiblen leeren Container mit Containern (likevector<vector<int>>
) für den Rückgabewert über die Referenz.In der ersten Version des Programms gab es
R.clear;()
als erste Anweisung, dass der Container mit Containern nicht leer sein musste. Peter Cordes meinte, dies könnte in die Spezifikation eingehen, und verwarf dafür 10 Byte.Probieren Sie es online!
Ungolfed:
quelle
R.clear()
, wenn Sie das weglassen , und den Anrufer lediglich auffordern, mit einem leeren Container zu beginnen.Python 2 , 88 Bytes
-4 Bytes dank Arnold Palmer
Probieren Sie es online!
Lösung ähnlich wie @ w0lf's haskell [antwort] [1]
Seltener Anwendungsfall für den
for-else
BauDurchsuchen Sie sortierte Listen
for l in r
(am Anfang leer).Wenn das Element (aus der Eingabe)
i
größer als das letzte Element der Liste istl[-1]
, fügen Sie der Liste ein Element hinzul+=[i]
und brechen Sie.Wenn keine Liste akzeptiert wurde, fügen Sie mit diesem Element eine neue Liste hinzu
r+=[[i]]
quelle
R, Work in progress (89, aber nicht erfolgreich)
Ich habe hier einige Arbeiten ausgeführt, weil ich mich mit
%in%
(es schlägt bei doppelten Einträgen fehl, insbesondere beim letzten Testfall) in eine Ecke zurück und ich muss jetzt andere Dinge tun, aber dies ist hier, wenn jemand darauf aufbauen möchte:Ungolfed:
quelle
z=function(x)"if"(sum(x|1),{a=x[(i=x>=cummax(x))] c(list(a),z(x[!i]))},NULL)
Werke]
undc
ist ein Zeilenumbruch (oder Semikolon)"if"
zuvor gesehen , aber ich bin ziemlich neu in R Golf. Du solltest als deine eigene Antwort posten, und ich kann meine abbauen. Mir gefällt, was Sie mit demi
Index gemacht haben, um das%in%
Problem zu umgehen.cummax
!JavaScript (ES6),
717068 BytesGanz einfach, iteriert einfach das Array, sucht nach dem ersten inneren Array, dessen letzter Wert
<=
auf den nächsten zu löschenden Wert verweist. Wenn keiner vorhanden ist, füge ein neues inneres Array mit dem nächsten Wert an die Ausgabe an, andernfalls füge den nächsten Wert an den ersten an inneres Array gefunden, das der Bedingung entspricht.Aktualisierung
Dank Neil, gespeichert drei Bytes Umwandlung
(...,o)
zu...&&o
und wieder die Organisation des Rückrufsmap()
kompakter zu sein.quelle
&&o
ist ein Byte kürzer als(,o)
.[...b].pop()
, aber ich denke, sie(o.find(b=>[...b].pop()<=n)||(n=[n],o)).push(n)
erspart dir ein oder zwei Bytes.Japt , 29 Bytes
Online testen!
quelle
C (gcc) ,
176175173 BytesProbieren Sie es online!
Etwas lesbare Version:
quelle
PHP,
911039685 Bytes(Bearbeitet, um 12 Zeichen hinzuzufügen
print_r($r);
, um die Ausgabeanforderung zu erfüllen.)(Bearbeitet, um 7 Bytes zu entfernen, wenn PHP-Fehler zugelassen werden.)
(Bearbeitet, um 11 Bytes zu entfernen, wenn die Zuweisung weiter ausgeführt wird.)
Bei einer gegebenen Eingabe
$a
wird ein Ergebnis erzeugt$r
Ziemlich:
Die pseudo-rekursive äußere Schleife initialisiert die Keep-
$b
und Discard-$d
Arrays so, dass sie leer sind, führt dann eine einfache Drop-Sort-Schleife durch, wobei die Discards schließlich als neue Eingabe festgelegt und die Keeps zum Ergebnis hinzugefügt werden$r
quelle
PHP ,
102 Bytes, 98 BytesProbieren Sie es online!
-4 Bytes, danke an @Umbrella
Erläuterung
Die Funktion nimmt die Eingabeliste als Array.
$s
wird als statisch deklariert. Dies erweitert den Gültigkeitsbereich auf alle Aufrufe dieser Funktion, sodass die Funktion rekursiv aufgerufen werden kann, ohne dass diese Ergebnisliste als Argument übergeben oder zurückgegeben werden muss.Durchlaufen Sie jeden Wert in der Liste.
Ist es weniger als das größte aktuelle Listenmitglied?
Ja,
$f
zur weiteren Sortierung auf die Liste setzen .Nein, setzen Sie es auf die Liste
$l
.Liste
$l
auf die Liste der Listen schieben.Wenn etwas in der Liste enthalten ist
$f
, senden Sie es zur weiteren Sortierung erneut.Gibt die Liste der Listen zurück.
quelle
<?php function d($a){return$r;}
, hast du mich von Herzen vernichtet. Abgesehen davon habe ich gerade gemerkt, dass wir beide vergessen haben, etwas auszugeben.$v<max($l)?$f[]=$v:$l[]=$v;
mit${$v<max($l)?f:l}[]=$v;
- zumindest, es funktioniert in meinen Tests.Salbei, 102 Bytes
Sehr ähnlich der Antwort von @Dead Possum .
Hängt jedes Mitglied
x
vonw
an die erste Liste ina
{list of lists} mitx
mehr als dem letzten Element an.wenn keine, anhängt
[x]
zua
.Ich würde es wirklich mögen, wenn
exists
zurückgegeben,a
wenn nichts gefunden wurde! Auch versuchen, @ officialaimms einzeilige Idee anzuwenden ...Frage: Wenn ich meinen Code aus der Funktion entfernt hätte, müsste ich die
w
Eingabe richtig zuordnen ? Würde es Bytes sparen?quelle
Ocaml ,
6962 BytesErläuterung:
quelle
APL,
1008883797857567776 Bytes-0 Bytes dank Kritixi Lithos ...
Probieren Sie es online!
Es muss etwas besserer Weg, dies zu tun ( Es gibt ). Alle Tipps sind sehr dankbar und willkommen.
Wie?
(Beachten Sie, dass einige dieser Erklärungen möglicherweise falsch sind, da ich vergessen habe, wie das funktioniert.)
quelle
{⍬≢⍴⍵}
kann werden(⍬≢⍴)
{(⍵/⍨~E),⊂⍵/⍨E←(⍬≡⍴)¨⍵}
? Es scheint von allem anderen getrennt zu sein[[1,2,5,7],[4],3]
der erforderliche[[1,2,5,7],[4],[3]]
.(,¨)
Gelee, 26 Bytes
Dies ist die gleiche Methode wie die APL-Antwort von Marinus.
Probieren Sie es online! .
quelle
JavaScript (Node.js) ,
125109106 Bytes-
1618 Bytes von Zacharý-1 durch Entfernen
{
und}
durch Ändern des Inkrementierers, um die "zuletzt auf die aktuelle" zu setzenGrundsätzlich fragt ist das aktuelle Element größer als das letzte Element, zur ersten Liste hinzufügen. Andernfalls fügen Sie zur zweiten hinzu.
Stellen Sie dabei fest, dass der Vergleich einer beliebigen Zahl
NaN
immer das Ergebnis istfalse
. Interessant!Erläuterung:
Probieren Sie es online!
quelle
var
?x
.