Jak opisano w tym pytaniu :

Dropsort, zaprojektowany przez Davida Morgana-Mar, jest przykładem „algorytmu sortowania” w czasie liniowym, który tworzy listę, która jest faktycznie posortowana, ale zawiera tylko niektóre oryginalne elementy. Każdy element, który nie jest co najmniej tak duży, jak maksymalna liczba elementów poprzedzających, jest po prostu usuwany z listy i odrzucany.

Aby użyć jednego ze swoich przypadków testowych, wejście z {1, 2, 5, 4, 3, 7}wydajnością {1, 2, 5, 7}, jak 4i 3oba spadły za to, że mniejsze niż poprzednio „posortowane” wartości 5.

Nie chcemy algorytmów „sortujących”, chcemy, żeby były prawdziwą okazją. Dlatego chcę, abyś napisał program, który, biorąc pod uwagę listę liczb, wyświetla listę list DropSorted (aby być kompletnym algorytmem sortowania, musielibyśmy scalić te listy, ale wcześniej scalono dwie listy posortowane i prośba o zrobienie tego ponownie to prawie dwa pytania, więc to pytanie jest konkretnie krokiem „podziału” naszego kompletnego DropSortu).

Rozmieszczenie i zawartość naszych list jest jednak kluczowa. Dane wyjściowe programu muszą odpowiadać wynikom DropSort, a następnie DropSort odrzuconych wartości i tak dalej, dopóki nie będzie tylko listy posortowanych łańcuchów. Ponownie, pożyczając istniejący zestaw testów (i dodając dwa kolejne):

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

Możesz założyć, że dane wejściowe nie są puste.

To jest golf golfowy , więc obowiązują standardowe zasady!

MATL , 15 10 9 bajtów

5 bajtów mniej przy użyciu pomysłu @beaker na łączne maksimum

t"ttY>=&)

Dane wejściowe to numeryczny wektor wiersza w formacie [1, 2, 5, 4, 3, 7](przecinki są opcjonalne). Dane wyjściowe zawierają listy oddzielone znakiem nowej linii, a liczby na każdej liście są oddzielone spacjami.

Wypróbuj online! Lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie

Biorąc pod uwagę tablicę, kod wybiera z niej każdy wpis, który jest równy skumulowanemu maksimum do tego wpisu.

Na przykład dane

1 2 5 4 3 7

kod wybiera pierwszy, drugi, trzeci i szósty wpis:

1 2 5     7

Następnie proces powtarza się na podtablicy utworzonej przez pozostałe wpisy (w oryginalnej kolejności):

      4 3

Należy to zrobić, dopóki podtablica pozostałych wpisów nie będzie pusta. Górną granicą wymaganej liczby iteracji jest rozmiar wejściowy. Ostatnie iteracje mogą nie być potrzebne. W takim przypadku działają one na pustej tablicy, wytwarzając dodatkowe puste tablice.

Na końcu stos zawiera wymagane tablice i prawdopodobnie kilka pustych tablic, które w ogóle nie są wyświetlane.

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

Haskell, 67 59 58 bajtów

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

Objaśnienie: Biorąc pod uwagę listę list (które są już posortowane) i wartość x, !operator umieści xna końcu pierwszej listy, której ostatni element jest mniejszy lub równy x. Jeśli taka lista nie istnieje, lista [x]jest umieszczana na końcu.

Wypróbuj online.

Łuska , 10 bajtów

hUmü<¡Ṡ-ü<

Wypróbuj online!

Jest to kombinacja mojej drugiej odpowiedzi Husk i odpowiedzi Xnora Haskella . Duplikat ü<wydaje się niezręczny, ale nie wiem, jak się go pozbyć ...

Wyjaśnienie

Funkcja ü<tłumaczy się nubBy(>)w języku Haskell. Przechodzi przez listę od lewej do prawej, zachowując te elementy, dla których żaden wcześniej przechowywany element nie jest ściśle większy. Innymi słowy, wykonuje droport. Pozostałe elementy uzyskuje się, biorąc różnicę listy oryginalnej listy i wynik ü<.

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

Haskell , 50 bajtów

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

Wypróbuj online!

Łuska , 16 bajtów

hUm₁≤¡₁>
ṠfSz⁰G▲

Wypróbuj online!

Wyjaśnienie

Ten pierwszy wiersz jest funkcją główną, a drugi to funkcja pomocnicza wyższego rzędu (przyjmuje funkcję jako argument i zwraca nową funkcję). Jest dostępny przez indeks dolny ₁. Chodzi o to, że ₁≤wykonuje droport i ₁>daje resztki elementów.

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

W głównej funkcji ₁>iterujemy funkcję resztek i stosujemy funkcję droport ₁≤do wyników.

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

Python 3 , 131 112 103 95 bajtów

Wielkie dzięki @Mr. Xcoder dla oszałamiającej 19 bajtów !!

Wielkie dzięki @ovs za niesamowite 17 bajtów!

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

Wypróbuj online!

Wyjaśnienie:

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

Haskell , 113 107 102 92 bajtów

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

Wypróbuj online!

To jest naprawdę długie.

Wyjaśnienie

!wykonuje sortowanie upuszczone na liście, a jednocześnie #zbiera ozdoby. gnastępnie stosuje się wielokrotnie, #aż lista będzie pusta, zapisując wyniki na liście.

APL, 27 bajtów

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

Wyjaśnienie:

• ⍵≡⍬:⍬: jeśli dane wejściowe są puste, zwróć pustą listę
• X←⍵≥⌈\⍵: wszystkie liczby większe lub równe bieżącemu maksimum
• (⊂X/⍵): lista tych liczb,
• ∇⍵/⍨~X: następuje wynik działania tej funkcji na pozostałych liczbach

JavaScript (ES6), 64 bajty

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

Nie golfowany:

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
  ]

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

console.log(JSON.stringify(f([1, 2, 5, 4, 3, 7])));     // [1, 2, 5, 7][4][3]
console.log(JSON.stringify(f([10, -1, 12])));           // [10, 12][-1]
console.log(JSON.stringify(f([-7, -8, -5, 0, -1, 1]))); // [-7, -5, 0, 1][-8, -1]
console.log(JSON.stringify(f([9, 8, 7, 6, 5])));        // [9][8][7][6][5]
console.log(JSON.stringify(f([10, 13, 17, 21])));       // [10, 13, 17, 21]
console.log(JSON.stringify(f([10, 10, 10, 9, 10])));    // [10, 10, 10, 10][9]
console.log(JSON.stringify(f([5, 4, 3, 8, 7, 6])));     // [5, 8][4, 7][3, 6]
console.log(JSON.stringify(f([0, 2, 5, 4, 0, 7])));     // [0,2,5,7],[4],[0]

R , 61 bajtów

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

Wypróbuj online!

Funkcja rekurencyjna. sum(x|1)jest skrótem length(x), więc ta rekurencja będzie działać, dopóki nie xbędzie pusta. cummaxprzyjmuje skumulowane maksimum x, które następnie porównuje się xponownie. W ten sposób powstaje wektor boolowski o długości x, w którym wszystkie PRAWDA odpowiadają posortowanym wartościom. Używamy tego, aby wziąć podzbiór xi printto. Funkcja jest następnie wywoływana ponownie w pozostałej części x.

Java 8, 182 179 177 bajtów

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 bajty dzięki @Nevay .
-2 bajty przy użyciu Stackzamiast Vector.

Wyjaśnienie:

Wypróbuj tutaj.

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

C #, 188 203 bajtów

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

Liczba bajtów obejmuje +18 dla:

using System.Linq;

Wypróbuj online!

C ++ 14, 118 108 bajtów

Wykorzystanie algorytmu z odpowiedzi Haskell w0lf .

Jako nienazwana ogólna lambda. Pierwszy parametr jest pojemnikiem wartości do droportowania (podobnie vector<int>), a drugi parametr wymaga zgodnego pustego pojemnika pojemników (podobnie vector<vector<int>>) dla wartości zwracanej przez odniesienie.

W pierwszej wersji programu była R.clear;()pierwsza instrukcja, dzięki czemu pojemnik z kontenerami nie musiał być pusty. Peter Cordes pomyślał, że to może być zgodne ze specyfikacją, więc do tego doszło 10 bajtów.

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

Wypróbuj online!

Nie golfowany:

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

Python 2 , 88 bajtów

-4 bajty dzięki Arnoldowi Palmerowi

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

Wypróbuj online!

Rozwiązanie podobne do haskell @ w0lf [odpowiedź] [1]

Rzadkie zastosowanie do for-elsebudowy

Iteruj przez posortowane listy for l in r(puste na początku).
Jeśli element (z wejścia) ijest większy niż ostatni element listy l[-1], dodaj element do listy l+=[i], przerwij.
Jeśli żadna lista nie została zaakceptowana, dodaj nową listę z tymi elementamir+=[[i]]

R, Prace w toku (89, ale nieudane)

Trzymam tu trochę pracy, ponieważ cofnąłem się w kąt za pomocą %in%(nie powiela się na zduplikowanych wpisach, w szczególności w ostatnim przypadku testowym), i muszę teraz zrobić inne rzeczy, ale jest to tutaj, jeśli ktoś chce na tym oprzeć:

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

Nie golfowany:

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

JavaScript (ES6), 71 70 68 bajtów

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

Całkiem proste, po prostu iteruje tablicę, szuka pierwszej tablicy wewnętrznej, której ostatnią wartością jest <=następna wartość do upuszczenia, jeśli żadna nie istnieje, dołącz nową tablicę wewnętrzną z następną wartością do wyjścia, w przeciwnym razie dołącz następną wartość do pierwszej znaleziono wewnętrzną tablicę pasującą do warunku.

Aktualizacje

Dzięki Neil uratował trzy bajty konwersja (...,o)do ...&&oi ponowne zorganizowanie oddzwanianie do map()być bardziej zwarta.

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}

Japt , 29 bajtów

@lOpP)<1}a@=f_<VªOoV=Z+S}V=Ug

Przetestuj online!

C (gcc) , 176 175 173 bajtów

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

Wypróbuj online!

Nieco czytelna wersja:

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

PHP, 91 103 96 85 bajtów

(Edytowano, aby dodać 12 znaków, print_r($r);aby spełnić wymaganie danych wyjściowych)
(Edytowano, aby usunąć 7 bajtów, gdy zezwala się na błędy PHP)
(Edytowano, aby usunąć 11 bajtów, gdy grasz zadanie dalej)

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

Dane wejściowe $adają wynik$r

Ładny:

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

Pseudo-rekurencyjna zewnętrzna pętla inicjuje tablice keep $bi discard, $daby opróżnić, a następnie wykonuje podstawową pętlę sortowania drop, w końcu ustawiając odrzucenia jako nowe dane wejściowe i dodając Keep do wyniku$r

PHP , 102 bajty , 98 bajtów

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

Wypróbuj online!

-4 bajty, dzięki @Umbrella

Wyjaśnienie

<?php

Ta funkcja przyjmuje listę wejściową jako tablicę.

function s($i) {

$s, która stanie się ostatecznie zwracaną listą, jest zadeklarowana jako statyczna. To rozszerza jego zakres na wszystkie wywołania tej funkcji, umożliwiając wywoływanie funkcji rekurencyjnie bez konieczności przekazywania tej listy wyników jako argumentu lub jej zwracania.

    static $s;

Pętlę przez każdą wartość na liście.

    foreach ($i as $v)

Czy to mniej niż największy aktualny członek listy?

        $v < max($l) ?

Tak, umieść go na liście w $fcelu dalszego sortowania.

                        $f[] = $v :

Nie, umieść to na liście $l.

                        $l[] = $v;

Wciśnij listę $lna listę list.

    $s[] = $l;

Jeśli jest coś na liście $f, wyślij go ponownie w celu dalszego sortowania.

    !$f ?: s($f);

Zwróć listę list.

    return $s;
}

Szałwia, 102 bajty

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

Bardzo podobny do @Dead Possum za odpowiedź .
Dołącza każdemu członkowi xz wpierwszego wykazu w a{} listy list z xwiększą niż jest to ostatni element.
jeśli nie, dołącza [x]do a.

Naprawdę chciałbym, jeśli existszwrócony a, jeśli nic nie zostało znalezione! Próbuję również zastosować pomysł @ lineaimm w jednym wierszu ...

Pytanie: Gdybym usunął kod z funkcji, musiałbym przypisać wdo wprowadzania danych, prawda? Czy to by oszczędzało bajty?

Ocaml , 69 62 bajtów

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

Wyjaśnienie:

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

APL, 100 88 83 79 78 57 56 77 76 bajtów

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

-0 bajtów dzięki Kritixi Lithos ...

Wypróbuj online!

Musi istnieć lepszy sposób na zrobienie tego ( jest ). Wszelkie wskazówki są bardzo mile widziane i mile widziane.

W jaki sposób?

(Uwaga, niektóre z tych wyjaśnień mogą być błędne, ponieważ zapomniałem, jak to działa)

{⍵≡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)

Galaretka, 26 bajtów

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

Jest to ta sama metoda, co odpowiedź APL marinusa.

Wypróbuj online! .

JavaScript (Node.js) , 125 109 106 bajtów

- 16 18 bajtów z Zacharý

-1, usuwając {i }zmieniając moduł inkrementujący, tak aby zawierał „ustaw jako ostatni na bieżący”

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}

Zasadniczo pyta, czy bieżący element jest większy niż ostatni element, dodaj do pierwszej listy. W przeciwnym razie dodaj do drugiego.

Okazało się podczas tego, że porównanie dowolnej liczby NaNzawsze będzie skutkowało false. Ciekawy!

Wyjaśnienie:

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

Wypróbuj online!