Conforme descrito nesta pergunta :

O Dropsort, projetado por David Morgan-Mar, é um exemplo de um "algoritmo de classificação" de tempo linear que produz uma lista que é, de fato, classificada, mas contém apenas alguns dos elementos originais. Qualquer elemento que não seja pelo menos tão grande quanto o máximo dos elementos anteriores é simplesmente removido da lista e descartado.

Para usar um de seus casos de teste, uma entrada de {1, 2, 5, 4, 3, 7}rendimentos {1, 2, 5, 7}, como 4e 3são eliminados por serem menores que o valor "classificado" anteriormente 5,.

Não queremos algoritmos de "classificação", queremos que eles sejam o negócio real. Portanto, quero que você escreva um programa que, dada uma lista de números, produza uma lista de listas DropSorted (para ser um algoritmo de classificação completo, precisaríamos mesclar essas listas, mas a fusão de duas listas classificadas já foi feita antes, e pedir para você fazer de novo é quase duas perguntas; portanto, essa pergunta é especificamente a etapa "dividida" de nosso DropSort completo).

A organização e o conteúdo de nossas listas são cruciais, no entanto. A saída do seu programa deve ser equivalente à saída de um DropSort, seguida por um DropSort dos valores descartados e assim por diante, até que você tenha apenas uma lista de cadeias classificadas. Novamente, emprestando o conjunto de testes existente (e adicionando mais dois):

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

Você pode assumir que a entrada não está vazia.

Isso é código-golfe , então as regras padrão se aplicam!

MATL , 15 10 9 bytes

5 bytes de desconto usando a idéia de @ máximo cumulativo de @beaker

t"ttY>=&)

A entrada é um vetor de linha numérica, no formato [1, 2, 5, 4, 3, 7](vírgulas são opcionais). A saída contém listas separadas por novas linhas, com os números em cada lista separados por espaços.

Experimente online! Ou verifique todos os casos de teste .

Explicação

Dada uma matriz, o código seleciona todas as entradas iguais ao máximo acumulado até essa entrada.

Por exemplo, dado

1 2 5 4 3 7

o código seleciona as primeira, segunda, terceira e sexta entradas:

1 2 5     7

Em seguida, o processo é repetido na sub-matriz formada pelas entradas restantes (na ordem original):

      4 3

Isso precisa ser feito até que a sub-matriz das entradas restantes esteja vazia. Um limite superior no número necessário de iterações é o tamanho da entrada. As últimas iterações podem não ser necessárias. Nesse caso, eles operam em uma matriz vazia, produzindo matrizes vazias adicionais.

No final, a pilha contém as matrizes necessárias e possivelmente várias matrizes vazias, que não são exibidas.

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 bytes

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

Explicação: Dada uma lista de listas (que já estão classificadas) e um valor x, o !operador colocará xno final da primeira lista cujo último elemento seja menor ou igual a x. Se essa lista não existir, a lista [x]será colocada no final.

Experimente online.

Casca , 10 bytes

hUmü<¡Ṡ-ü<

Experimente online!

Esta é uma combinação da minha outra resposta Husk e a resposta Haskell de xnor . A cópia ü<parece desajeitada, mas não sei como me livrar dela ...

Explicação

A função é ü<traduzida nubBy(>)em Haskell. Ele percorre uma lista da esquerda para a direita, mantendo os elementos para os quais nenhum elemento mantido anteriormente é estritamente maior. Em outras palavras, ele executa dropsort. Os elementos restantes são obtidos considerando a diferença de lista da lista original e o resultado 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 bytes

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

Experimente online!

Casca , 16 bytes

hUm₁≤¡₁>
ṠfSz⁰G▲

Experimente online!

Explicação

Essa primeira linha é a função principal e a segunda é uma função auxiliar de ordem superior (assume uma função como argumento e retorna uma nova função). É acessado pelo subscrito ₁. A idéia é que ₁≤executa dropsort e ₁>fornece os elementos restantes.

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

Na função principal, ₁>iteramos a função restante e aplicamos a função dropsort ₁≤aos resultados.

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 bytes

Muito obrigado @Mr. Xcoder para esmagar 19 bytes !!

Muito obrigado @ovs por 17 bytes incríveis!

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

Experimente online!

Explicação:

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

Experimente online!

Isso parece muito longo.

Explicação

!executa a classificação de queda em uma lista, enquanto #coleta os aparamentos. gaplica-se repetidamente #até que a lista esteja vazia registrando os resultados em uma lista.

APL, 27 bytes

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

Explicação:

• ⍵≡⍬:⍬: se a entrada estiver vazia, retorne a lista vazia
• X←⍵≥⌈\⍵: todos os números maiores ou iguais ao máximo em execução
• (⊂X/⍵): a lista desses números,
• ∇⍵/⍨~X: seguido pelo resultado da execução dessa função nos números restantes

JavaScript (ES6), 64 bytes

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 bytes

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

Experimente online!

Função recursiva. sum(x|1)é uma abreviação de length(x), portanto, essa recursão será executada até que xesteja vazia. cummaxleva o máximo cumulativo de x, que é comparado com xnovamente. Isso produz um vetor booleano de comprimento x, onde todas as TRUEs correspondem a valores classificados. Nós usamos isso para tomar um subconjunto de xe print-lo. A função é chamada novamente no restante de x.

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 graças a @Nevay .
-2 bytes usando em Stackvez de Vector.

Explicação:

Experimente aqui.

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

A contagem de bytes inclui +18 para:

using System.Linq;

Experimente online!

C ++ 14, 118 108 bytes

Usando o algoritmo da resposta Haskell de w0lf .

Como lambda genérico sem nome. O primeiro parâmetro é um contêiner dos valores para dropsort (like vector<int>) e o segundo parâmetro requer um contêiner vazio compatível de contêineres (like vector<vector<int>>) para o valor de retorno por referência.

Na primeira versão do programa, havia R.clear;()como primeira instrução, de modo que o contêiner de contêineres não precisava estar vazio. Peter Cordes achou que isso poderia acontecer na especificação, deixando cair 10 bytes para isso.

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

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

Python 2 , 88 bytes

-4 bytes graças a 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

Experimente online!

Solução semelhante ao haskell de @ w0lf [resposta] [1]

Caso de uso raro para for-elseconstrução

Repita as listas ordenadas for l in r(vazias no início).
Se o elemento (da entrada) ifor maior que o último elemento da lista l[-1], inclua o elemento na lista l+=[i], quebre.
Se nenhuma lista foi aceita, adicione uma nova lista com esses elemensr+=[[i]]

R, Trabalho em andamento (89, mas com falha)

Segurando um pouco de trabalho aqui, porque eu me apoiei em um canto usando %in%(ele falha em entradas duplicadas, em particular no último caso de teste), e eu preciso fazer outras coisas agora, mas isso está aqui se alguém quiser criar:

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

Muito simples, apenas itera a matriz, procura a primeira matriz interna cujo último valor é <=o próximo valor a ser descartado, se não existir, anexa uma nova matriz interna com o próximo valor à saída, caso contrário, anexa o próximo valor à primeira encontrado matriz interna que corresponde à condição.

Atualizações

Graças a Neil, salvou três bytes converter (...,o)para ...&&oe re-organizar o retorno de chamada para map()ser mais compacto.

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}

Japonês , 29 bytes

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

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

Experimente online!

Versão um pouco legível:

#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

(Editado para adicionar 12 caracteres print_r($r);para atender aos requisitos de saída)
(Editado para remover 7 bytes ao permitir erros de PHP)
(Editado para remover 11 bytes ao continuar a tarefa)

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

Dada a entrada $a, produz resultado$r

Bonita:

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

O loop externo pseudo-recursivo inicializa as matrizes keep $be descarta $dpara esvaziar, em seguida, executa um loop básico de classificação da gota, definindo finalmente as devoluções como a nova entrada e adicionando as Keep ao resultado$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;}

Experimente online!

-4 bytes, graças a @Umbrella

Explicação

<?php

A função assume a lista de entrada como uma matriz.

function s($i) {

$s, que se tornará a lista de listas finalmente retornada, é declarada estática. Isso estende seu escopo a todas as chamadas dessa função, permitindo que a função seja chamada recursivamente sem precisar passar essa lista de resultados como argumento ou retorná-la.

    static $s;

Repita cada valor da lista.

    foreach ($i as $v)

É menor que o maior membro da lista atual?

        $v < max($l) ?

Sim, coloque-o na lista $fpara posterior classificação.

                        $f[] = $v :

Não, coloque-o na lista $l.

                        $l[] = $v;

Empurre a lista $lpara a lista de listas.

    $s[] = $l;

Se houver algo na lista $f, envie-o novamente para outra classificação.

    !$f ?: s($f);

Retorne a lista de listas.

    return $s;
}

Sábio, 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

Muito semelhante à resposta de @Dead Possum .
Anexa cada membro xda wà primeira lista em a{list of lists} com xmaior que o último elemento.
se nenhum, anexa [x]a a.

Eu realmente gostaria que fosse existsdevolvido ase nada fosse encontrado! Também tentando aplicar a ideia de uma linha de @ officialaimm ...

Pergunta: Se eu removesse meu código da função, teria que atribuir wa entrada, certo? Então, ele salvaria 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

Explicação:

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 graças a Kritixi Lithos ...

Experimente online!

Tem que haver uma maneira melhor de fazer isso ( existe ). Todas as dicas são muito apreciadas e bem-vindas.

Quão?

(Observe que algumas dessas explicações podem estar erradas, pois eu esqueci como isso funcionava)

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

Geléia, 26 bytes

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

Esse é o mesmo método da resposta do APL do marinus.

Experimente online! .

JavaScript (Node.js) , 125 109 106 bytes

- 16 18 bytes de Zacharý

-1 removendo {e }alterando o incrementador para incluir o "definir último para o atual"

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}

Basicamente, pede é o item atual maior que o último item, adicione à primeira lista. Caso contrário, adicione ao segundo.

Descobri durante isso que comparar qualquer número NaNsempre resultará false. Interessante!

Explicação:

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

Experimente online!