DropSort es wie es ist heiß

41

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 4und 3sind 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 , daher gelten die Standardregeln!

Lord Farquaad
quelle
Können wir gerne ausgeben [5, 4, 3, 8, 7, 6] -> [5, 8], [4,3,7,6]?
Mr. Xcoder
5
@Xcoder, nun, mir macht die Syntax nichts aus, aber Sie müssen die zweite Liste noch sortieren (und in diesem Fall aufteilen). Zu wissen, wann aufzuhören ist Teil der Herausforderung;). Und Stewie, ich weiß wirklich nicht, was ich dir sagen soll. Ich habe die DropSort-Herausforderung gesehen und dachte, das klingt nach Spaß. Hast du vielleicht deine Zeitmaschine benutzt, um diese Frage zu beantworten? Verwenden Sie es einfach nicht, um die beste Antwort zu sehen!
Lord Farquaad
Beachten Sie, dass durch das Hinzufügen der Sortierung der Reste die Lösungen nicht mehr linear sind.
Ikegami
Sollte {3,4,5,3,4,5,3,4,5}ergeben {{3,4,5,5,5},{3,4,4},{3}}?
QBrute
@QBrute Ich denke das ist richtig.
Lord Farquaad

Antworten:

10

MATL , 15 10 9 Bytes

5 Bytes weniger , wenn die Idee des kumulativen Maximums von @beaker verwendet wird

t"ttY>=&)

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

1 2 5 4 3 7

Der Code wählt den ersten, zweiten, dritten und sechsten Eintrag aus:

1 2 5     7

Anschließend wird der Vorgang in dem aus den verbleibenden Einträgen gebildeten Unterfeld wiederholt (in der ursprünglichen Reihenfolge):

      4 3

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.

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
quelle
23

Haskell, 67 59 58 Bytes

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

Erläuterung: Bei einer gegebenen Liste von Listen (die bereits sortiert sind) und einem Wert xwird der !Operator xam Ende der ersten Liste platziert, deren letztes Element kleiner oder gleich ist x. Wenn keine solche Liste vorhanden ist, wird die Liste [x]am Ende platziert.

Probieren Sie es online aus.

Cristian Lupascu
quelle
3
Dies ist eine unglaublich clevere Lösung. Ich habe ehrlich gesagt erwartet, dass die meisten Leute DropSort immer und immer wieder verwenden, bis nichts mehr übrig ist, aber ich hoffte, jemand würde sich einen kreativeren Weg einfallen lassen.
Lord Farquaad
13

Schale , 10 Bytes

hUmü<¡Ṡ-ü<

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

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
quelle
10
Outgolfs Top-Antwort von 33% "Ich weiß nicht, es fühlt sich klobig"
Lord Farquaad
11

Haskell , 50 Bytes

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

Probieren Sie es online!

xnor
quelle
1
Ich hatte fast das, wusste nur nicht die \\ Funktion: (
H.PWiz
2
Oh das ist ja eine sehr handliche Funktion! Sehr schöne Lösung =)
Fehler
7

Schale , 16 Bytes

hUm₁≤¡₁>
ṠfSz⁰G▲

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.

Ṡ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].

In der Hauptfunktion iterieren wir ₁>die Restfunktion und wenden die Dropssort-Funktion ₁≤auf die Ergebnisse an.

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
quelle
Schale ist das neue Gelee ...
Erik der Outgolfer
1
@EriktheOutgolfer von MATL geschlagen. : /
Zgarb
6

Python 3 , 131 112 103 95 Bytes

Vielen Dank @Mr. Xcoder für unglaubliche 19 Bytes !!

Vielen Dank an @ovs für unglaubliche 17 Bytes!

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

Probieren Sie es online!

Erläuterung:

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
quelle
2
116 Bytes. Die if-elsekann zusammengeklappt werden [m,d][i<m[-1]]+=[i].
Mr. Xcoder
Woah, vielen Dank ... Ich habe das [m,d]Ding ausprobiert, aber es hat irgendwie nicht funktioniert ...
offiziell
1
113 Bytes . (len(d)>0)ist bool(d), weil leere Listen in Python falsch sind. +1, nette Lösung!
Mr. Xcoder
1
95 Bytes
OVS
2
i,ist nur eine Abkürzung für (i,), die ein Tupel enthält a. a,*x = x or [0]ist das erweiterte Entpacken von python3 . Hier ist ein hilfreicher SO-Beitrag zu diesem Thema mit einigen Beispielen.
Ovs
6

Haskell , 113 107 102 92 Bytes

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=[]

Probieren 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. gwird dann wiederholt angewendet, #bis die Liste leer ist, und die Ergebnisse in einer Liste aufgezeichnet.

Weizen-Assistent
quelle
1
Durch Ersetzen head adurch wird a!!0ein Byte gespeichert.
Tomsmeding
5

APL, 27 Bytes

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

Erläuterung:

  • ⍵≡⍬:⍬: Wenn die Eingabe leer ist, geben Sie die leere Liste zurück
  • X←⍵≥⌈\⍵: 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 Nummern
Marinus
quelle
Speichern Sie ein Byte mit {⍵≡⍬:⍬⋄(⊂⍵~r),∇r←⍵/⍨⍵<⌈\⍵}. Morten macht sich Sorgen, dass er nicht auf seine E-Mails reagiert. Ist alles in Ordnung?
Adám
Ach je. Ich bin froh, dass du es geschafft hast. Bis nächste Woche.
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)]

Ungolfed:

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
quelle
1
Für den ?!
Neil
Ha, ja, ich hätte eine Erklärung hinzufügen sollen. Jetzt hinzugefügt.
Rick Hitchcock
@ Neil?!
Patrick Roberts
(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önnen f=Ihren Code entfernen , und vielleicht gibt Ihnen mein Code einige Ideen, wie Sie Ihren noch weiter verbessern können.
David Archibald
Danke, @DavidArchibald. Ich kann 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.
Rick Hitchcock
4

R , 61 Bytes

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

Probieren Sie es online!

Rekursive Funktion. sum(x|1)ist eine Abkürzung für length(x), daher wird diese Rekursion ausgeführt, bis sie xleer ist. cummaxnimmt das kumulative Maximum von x, das dann wieder verglichen xwird. Dies erzeugt einen booleschen Längenvektor x, bei dem alle TRUEs sortierten Werten entsprechen. Wir verwenden das, um eine Teilmenge von xund zu nehmen print. Im Übrigen wird die Funktion dann erneut aufgerufen x.

JAD
quelle
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 Bytes dank @Nevay .
-2 Bytes mit Stackanstelle von Vector.

Erläuterung:

Probieren Sie es hier aus.

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
quelle
Können Sie verwenden, try{}catch{}anstatt zu prüfen, gegen l.size()einige zu speichern?
TheLethalCoder
1
Sie können die innere Schleife bei beginnen 0und die Klammern der äußeren for-Schleife entfernen 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 Bytes).
Nevay
3

C #, 188 203 Bytes

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();}

Die Byteanzahl umfasst +18 für:

using System.Linq;

Probieren Sie es online!

DerLethalCoder
quelle
@RickHitchcock Auf Kosten von 15 Bytes behoben! Schöner Ort.
TheLethalCoder
Gute Arbeit :) +1
Rick Hitchcock
3

C ++ 14, 118 108 Bytes

Verwenden 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 (like vector<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.

[](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:;}}

Probieren Sie es online!

Ungolfed:

[](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
quelle
Sie können wahrscheinlich davonkommen R.clear(), wenn Sie das weglassen , und den Anrufer lediglich auffordern, mit einem leeren Container zu beginnen.
Peter Cordes
@PeterCordes gute Idee, ich könnte meine anderen C ++ - Antworten, die die Rückgabe über Referenzparameter enthielten, respektieren.
Karl Napf
2

Python 2 , 88 Bytes

-4 Bytes dank 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

Probieren Sie es online!

Lösung ähnlich wie @ w0lf's haskell [antwort] [1]

Seltener Anwendungsfall für den for-elseBau

Durchsuchen Sie sortierte Listen for l in r(am Anfang leer).
Wenn das Element (aus der Eingabe) igrößer als das letzte Element der Liste ist l[-1], fügen Sie der Liste ein Element hinzu l+=[i]und brechen Sie.
Wenn keine Liste akzeptiert wurde, fügen Sie mit diesem Element eine neue Liste hinzur+=[[i]]

Totes Opossum
quelle
1
88 Bytes, indem Sie es einfach aus seiner Funktion nehmen.
Arnold Palmer
1

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:

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

Ungolfed:

z=function(x){
  if(length(x)){
    a=x[x>=cummax(x)]
    append(list(a),z(x[!(x%in%a)]))
  } else {
    NULL
  }
}
Alex Axthelm
quelle
Sie sollten dies wahrscheinlich vorerst löschen, damit Sie keine Abstimmungen erhalten, während Sie das Problem beheben.
Giuseppe
1
z=function(x)"if"(sum(x|1),{a=x[(i=x>=cummax(x))] c(list(a),z(x[!i]))},NULL)Werke
Giuseppe
Das Leerzeichen zwischen ]und cist ein Zeilenumbruch (oder Semikolon)
Giuseppe
Ich habe noch nie "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 dem iIndex gemacht haben, um das %in%Problem zu umgehen.
Alex Axthelm
Nein, du hast die ganze harte Arbeit gemacht! Ich konnte mich nicht mit diesem Problem auseinandersetzen, bis ich Ihre Implementierung sah - ich hätte mich nie daran erinnert cummax!
Giuseppe
1

JavaScript (ES6), 71 70 68 Bytes

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

Ganz 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 ...&&ound wieder die Organisation des Rückrufs map()kompakter zu sein.

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
quelle
1
&&oist ein Byte kürzer als (,o).
Neil
@ Neil Gah! Toller Fang, danke
Patrick Roberts
1
Ich mag deine [...b].pop(), aber ich denke, sie (o.find(b=>[...b].pop()<=n)||(n=[n],o)).push(n)erspart dir ein oder zwei Bytes.
Neil
Bei diesem Tempo fühle ich mich verpflichtet, dies als Community-Post zu kennzeichnen ... verdammt
Patrick Roberts
Nur wegen ein paar Verbesserungen? Es ist im Grunde immer noch der gleiche Code ...
Neil
1

C (gcc) , 176 175 173 Bytes

#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("");}}

Probieren Sie es online!

Etwas lesbare Version:

#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
quelle
175 Bytes .
Mr. Xcoder
Äh, natürlich, wie dumm - danke!
Felix Palmen
1

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

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

Bei einer gegebenen Eingabe $awird ein Ergebnis erzeugt$r

Ziemlich:

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

Die pseudo-rekursive äußere Schleife initialisiert die Keep- $bund Discard- $dArrays 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

Regenschirm
quelle
1

PHP , 102 Bytes , 98 Bytes

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

Probieren Sie es online!

-4 Bytes, danke an @Umbrella

Erläuterung

<?php

Die Funktion nimmt die Eingabeliste als Array.

function s($i) {

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

    static $s;

Durchlaufen Sie jeden Wert in der Liste.

    foreach ($i as $v)

Ist es weniger als das größte aktuelle Listenmitglied?

        $v < max($l) ?

Ja, $fzur weiteren Sortierung auf die Liste setzen .

                        $f[] = $v :

Nein, setzen Sie es auf die Liste $l.

                        $l[] = $v;

Liste $lauf die Liste der Listen schieben.

    $s[] = $l;

Wenn etwas in der Liste enthalten ist $f, senden Sie es zur weiteren Sortierung erneut.

    !$f ?: s($f);

Gibt die Liste der Listen zurück.

    return $s;
}
WebSmithery
quelle
1
Unter Berücksichtigung der 31 Zeichen, die ich ausgelassen habe <?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.
Umbrella
Ich habe meine Lösung wurde Golf bis zu schlagen Sie versuchen , ohne Sie mit und ich fand ein Weg Sie verbessert werden: Ich denke , Sie vier Zeichen durch Ersetzen sparen können $v<max($l)?$f[]=$v:$l[]=$v;mit ${$v<max($l)?f:l}[]=$v;- zumindest, es funktioniert in meinen Tests.
Umbrella
@Umbrella, kehrt nicht zurück, gibt aus ??? Und danke für die 4 Bytes. Ich denke nie daran, so zu arbeiten und Code zu verwenden, um den Variablennamen auszuwerten. Ich muss daran denken, dass in zukünftigen Herausforderungen……
WebSmithery
Gefunden, scheint der Konsens die Rückgabe als Ausgabe zu akzeptieren: codegolf.meta.stackexchange.com/questions/2447/…
Umbrella
0

Salbei, 102 Bytes

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

Sehr ähnlich der Antwort von @Dead Possum .
Hängt jedes Mitglied xvon wan die erste Liste in a{list of lists} mit xmehr als dem letzten Element an.
wenn keine, anhängt [x]zu a.

Ich würde es wirklich mögen, wenn existszurückgegeben, awenn nichts gefunden wurde! Auch versuchen, @ officialaimms einzeilige Idee anzuwenden ...

Frage: Wenn ich meinen Code aus der Funktion entfernt hätte, müsste ich die wEingabe richtig zuordnen ? Würde es Bytes sparen?

vielleicht so
quelle
0

Ocaml , 69 62 Bytes

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

Erläuterung:

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
quelle
0

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

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

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

{⍵≡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ý
quelle
{⍬≢⍴⍵}kann werden(⍬≢⍴)
Kritixi Lithos
Bereits getan, ohne Ihren Kommentar zu sehen,
Zacharý
Was ist der Zweck von {(⍵/⍨~E),⊂⍵/⍨E←(⍬≡⍴)¨⍵}? Es scheint von allem anderen getrennt zu sein
Kritixi Lithos
Ohne wäre der erste Testfall so etwas wie [[1,2,5,7],[4],3]der erforderliche [[1,2,5,7],[4],[3]].
Zacharý
Sie könnten in der Lage sein, diese dfn auf nur zu verkürzen (,¨)
Kritixi Lithos
0

Gelee, 26 Bytes

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

Dies ist die gleiche Methode wie die APL-Antwort von Marinus.

Probieren Sie es online! .

Zacharý
quelle
0

JavaScript (Node.js) , 125 109 106 Bytes

- 16 18 Bytes von Zacharý

-1 durch Entfernen {und }durch Ändern des Inkrementierers, um die "zuletzt auf die aktuelle" zu setzen

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}

Grundsä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 NaNimmer das Ergebnis istfalse . Interessant!

Erläuterung:

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

Probieren Sie es online!

Stan Strum
quelle
Müssen Sie verwenden var?
Zacharý
@ Zacharý, lass mich nachsehen!
Stan Strum
Die Eltern werden nicht gebraucht x.
Zacharý