Comme décrit dans cette question :

Dropsort, conçu par David Morgan-Mar, est un exemple d'un "algorithme de tri" à temps linéaire qui produit une liste qui est en fait triée, mais ne contient que certains des éléments d'origine. Tout élément qui n’est pas au moins aussi grand que le maximum des éléments qui le précèdent est simplement supprimé de la liste et supprimé.

Pour utiliser l' un de leurs cas de test, une entrée de {1, 2, 5, 4, 3, 7}rendements {1, 2, 5, 7}, comme 4et 3sont à la fois retranchée parce qu'elle est inférieure à la valeur précédemment « trié », 5.

Nous ne voulons pas de "tri" des algorithmes, nous voulons qu'ils soient la vraie affaire. Par conséquent, je veux que vous écriviez un programme qui, étant donné une liste de numéros, produit une liste de listes DropSorted (comme un algorithme de tri complet, nous aurions besoin de fusionner ces listes, mais la fusion de deux listes triées a été fait avant, et vous demander de le refaire, c'est à peu près poser deux questions, cette question est donc précisément l'étape de "fractionnement" de notre liste déroulante complète).

La disposition et le contenu de nos listes sont toutefois cruciaux. La sortie de votre programme doit être équivalente à la sortie d'un DropSort, suivi d'un DropSort des valeurs ignorées, et ainsi de suite jusqu'à ce que vous n'ayez plus qu'une liste de chaînes triées. Encore une fois, en empruntant la suite de tests existante (et en ajoutant deux autres):

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

Vous pouvez supposer que l'entrée est non vide.

C'est code-golf , donc les règles standard s'appliquent!

MATL , 15 10 9 octets

5 octets en dehors de l'idée de @beaker du maximum cumulatif

t"ttY>=&)

L'entrée est un vecteur de ligne numérique, au format [1, 2, 5, 4, 3, 7] (les virgules sont facultatives). La sortie contient des listes séparées par des lignes, les numéros de chaque liste étant séparés par des espaces.

Essayez-le en ligne! Ou vérifiez tous les cas de test .

Explication

Étant donné un tableau, le code sélectionne chaque entrée égale au maximum cumulatif jusqu’à cette entrée.

Par exemple, étant donné

1 2 5 4 3 7

le code sélectionne les première, deuxième, troisième et sixième entrées:

1 2 5     7

Ensuite, le processus est répété sur le sous-réseau formé par les entrées restantes (dans l'ordre d'origine):

      4 3

Cela doit être fait jusqu'à ce que le sous-tableau des entrées restantes soit vide. Une limite supérieure sur le nombre requis d'itérations est la taille d'entrée. Les dernières itérations peuvent ne pas être nécessaires. Dans ce cas, ils opèrent sur un tableau vide, produisant des tableaux supplémentaires vides.

A la fin, la pile contient les tableaux requis et éventuellement plusieurs tableaux vides, qui ne sont pas affichés du tout.

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 octets

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

Explication: À partir d'une liste de listes (déjà triées) et d'une valeur x, l' !opérateur place xà la fin de la première liste dont le dernier élément est inférieur ou égal à x. Si cette liste n'existe pas, elle [x]est placée à la fin.

Essayez-le en ligne.

Coque , 10 octets

hUmü<¡Ṡ-ü<

Essayez-le en ligne!

Ceci est une combinaison de mon autre réponse Husk et de la réponse Haskell de xnor . Le duplicata ü<semble maladroit, mais je ne sais pas comment m'en débarrasser ...

Explication

La fonction se ü<traduit par nubBy(>)en Haskell. Il parcourt une liste de gauche à droite en conservant les éléments pour lesquels aucun élément précédemment conservé n’est strictement supérieur. En d'autres termes, il effectue un dropsort. Les éléments restants sont obtenus en prenant la différence de liste de la liste originale et le résultat de ü<.

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 octets

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

Essayez-le en ligne!

Coque , 16 octets

hUm₁≤¡₁>
ṠfSz⁰G▲

Essayez-le en ligne!

Explication

Cette première ligne est la fonction principale et la seconde est une fonction d'assistance d'ordre supérieur (elle prend une fonction en tant qu'argument et renvoie une nouvelle fonction). Il est accessible par l'indice ₁. L'idée est que ₁≤effectue des dropsort et ₁>donne les éléments restants.

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

Dans la fonction principale, nous itérons la fonction restants ₁>et appliquons la fonction dropsort ₁≤aux résultats.

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 octets

Merci beaucoup @M. Xcoder pour un fracassant 19 octets !!

Merci beaucoup @ovs pour un nombre incroyable de 17 octets!

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

Essayez-le en ligne!

Explication:

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 octets

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

Essayez-le en ligne!

Cela semble vraiment long.

Explication

!effectue le tri sélectif sur une liste pendant la #collecte des rognages. gpuis à plusieurs reprises #jusqu'à ce que la liste soit vide en enregistrant les résultats dans une liste.

APL, 27 octets

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

Explication:

• ⍵≡⍬:⍬: si l'entrée est vide, retourne la liste vide
• X←⍵≥⌈\⍵: tous les nombres supérieurs ou égaux au maximum courant
• (⊂X/⍵): la liste de ces numéros,
• ∇⍵/⍨~X: suivi du résultat de l'exécution de cette fonction sur les nombres restants

JavaScript (ES6), 64 octets

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
  ]

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 octets

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

Essayez-le en ligne!

Fonction récursive. sum(x|1)est un raccourci pour length(x), donc cette récursion sera exécutée jusqu'à ce qu'elle xsoit vide. cummaxprend le maximum cumulatif de x, qui est ensuite comparé à xnouveau. Cela produit un vecteur booléen de longueur x, où tous les TRUE correspondent à des valeurs triées. Nous utilisons que de prendre un sous - ensemble xet printil. La fonction est ensuite rappelée le reste de x.

Java 8, 182 179 177 octets

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 octets grâce à @Nevay .
-2 octets en utilisant Stackau lieu de Vector.

Explication:

Essayez ici.

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 octets

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

Le nombre d'octets comprend +18 pour:

using System.Linq;

Essayez-le en ligne!

C ++ 14, 118 108 octets

Utilisation de l'algorithme de la réponse Haskell de w0lf .

En tant que lambda générique non nommé. Le premier paramètre est un conteneur des valeurs à abandonner (comme vector<int>) et le second paramètre nécessite un conteneur vide compatible de conteneurs (comme vector<vector<int>>) pour la valeur de retour via référence.

Dans la première version du programme, il y avait R.clear;()comme première déclaration, de sorte que le conteneur de conteneurs n'avait pas besoin d'être vide. Peter Cordes pensait que cela pourrait figurer dans la spécification, supprimant ainsi 10 octets.

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

Essayez-le en ligne!

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

Python 2 , 88 octets

-4 octets grâce à 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

Essayez-le en ligne!

Solution similaire à haskell de @ w0lf [réponse] [1]

Cas d'utilisation rare pour la for-elseconstruction

Parcourez les listes triées for l in r(vides au début).
Si element (from input) iest plus grand que le dernier élément de la liste l[-1], ajoutez un élément à la liste l+=[i], break.
Si aucune liste n'a été acceptée, ajouter une nouvelle liste avec cet elemensr+=[[i]]

R, travail en cours (89, mais échec)

Garder du travail ici, parce que je me %in%suis laissé aller dans un coin en utilisant (il échoue sur les entrées en double, en particulier le dernier cas de test), et je dois aller faire autre chose maintenant, mais ceci est ici si quelqu'un veut en tirer parti:

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

JavaScript (ES6), 71 70 68 bytes

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

Pretty simple, just iterates the array, looks for the first inner array whose last value is <= to the next value to drop, if none exists, append a new inner array with the next value to the output, otherwise append the next value to the first found inner array that matches the condition.

Updates

Thanks to Neil, saved three bytes converting (...,o) to ...&&o and re-organizing the callback to map() to be more compact.

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 bytes

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

Test it online!

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

Try it online!

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

PHP, 91 103 96 85 bytes

(Edited to add 12 chars of print_r($r); to meet requirement to output)
(Edited to remove 7 bytes when allowing PHP Errors)
(Edited to remove 11 bytes when golfing the assignment further)

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

Given input $a, it produces result $r

Pretty:

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

The pseudo-recursive outer loop initializes the keep $b and discard $d arrays to empty, then does a basic drop sort loop, finally setting the discards as the new input and adding the keeps to the result $r

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

Try it online!

-4 bytes, thanks to @Umbrella

Explanation

<?php

The function takes the input list as an array.

function s($i) {

$s, which will become the finally returned list of lists, is declared static. This extends its scope to all calls of this function, allowing the function to be called recursively without having to pass this result list as an argument or to return it.

    static $s;

Loop through each value in the list.

    foreach ($i as $v)

Is it less than the biggest current list member?

        $v < max($l) ?

Yes, put it on list $f for further sorting.

                        $f[] = $v :

No, put it on list $l.

                        $l[] = $v;

Push list $l onto the list of lists.

    $s[] = $l;

If there's anything in list $f, send it round again for further sorting.

    !$f ?: s($f);

Return the list of lists.

    return $s;
}

Sage, 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

Very similar to @Dead Possum's answer.
Appends each member x of w to the first list in a {list of lists} with x greater than it's last element.
if none, appends [x] to a.

I would really like it if exists returned a if nothing was found! Also trying to apply @officialaimm's one-line idea ...

Question: If I removed my code from the function, I'd have to assign w to input right? So would it save bytes?

Ocaml, 69 62 bytes

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

Explanation:

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 bytes

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

-0 bytes thanks to Kritixi Lithos...

Try it online!

There's got to be some better way to do this (There is). Any tips are very greatly appreciated and welcome.

How?

(Note, some of this explanation might be wrong, as I forgot how this worked)

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

Jelly, 26 bytes

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

This is the same method as marinus' APL answer.

Try it online!.

JavaScript (Node.js), 125 109 106 bytes

-16 18 bytes from Zacharý

-1 by removing { and } by changing the incrementer to include the "set last to the current"

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}

Basically, asks is the current item greater than the last item, add to the first list. Otherwise, add to the second.

Found out during this that comparing any number to NaN will always result false. Interesting!

Explanation:

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

Try it online!