Desafío

Dado un conjunto no entero de enteros, por ejemplo:

[5, 2, 7, 6, 4, 1, 3]

Primero sepárelo en matrices donde ningún elemento sea más grande que el anterior (es decir, matrices no ascendentes):

[5, 2] [7, 6, 4, 1] [3]

A continuación, invierta cada matriz:

[2, 5] [1, 4, 6, 7] [3]

Finalmente, concatenelos todos juntos:

[2, 5, 1, 4, 6, 7, 3]

Esto debería ser lo que su programa emite / devuelve. Repita este procedimiento suficientes veces y la matriz estará completamente ordenada.

Reglas

• La entrada y salida se pueden dar a través de cualquier método estándar, y pueden estar en cualquier formato de matriz razonable.
• La matriz de entrada nunca estará vacía, pero puede contener negativos y / o duplicados.
• El valor absoluto de cada entero siempre será menor que 2 ³¹ .

Casos de prueba

Esperemos que estos cubran todos los casos extremos:

[1] -> [1]
[1, 1] -> [1, 1]
[1, 2] -> [1, 2]
[2, 1] -> [1, 2]
[2, 3, 1] -> [2, 1, 3]
[2, 1, 3] -> [1, 2, 3]
[2, 1, 2] -> [1, 2, 2]
[2, 1, 1] -> [1, 1, 2]
[3, 1, 1, 2] -> [1, 1, 3, 2]
[3, 2, 1, 2] -> [1, 2, 3, 2]
[3, 1, 2, 2] -> [1, 3, 2, 2]
[1, 3, 2, 2] -> [1, 2, 2, 3]
[1, 0, 5, -234] -> [0, 1, -234, 5]
[1, 0, 1, 0, 1] -> [0, 1, 0, 1, 1]
[1, 2, 3, 4, 5] -> [1, 2, 3, 4, 5]
[5, 4, 3, 2, 1] -> [1, 2, 3, 4, 5]
[2, 1, 5, 4, 3] -> [1, 2, 3, 4, 5]
[2, 3, 1, 5, 4] -> [2, 1, 3, 4, 5]
[5, 1, 4, 2, 3] -> [1, 5, 2, 4, 3]
[5, 2, 7, 6, 4, 1, 3] -> [2, 5, 1, 4, 6, 7, 3]
[-5, -2, -7, -6, -4, -1, -3] -> [-5, -7, -2, -6, -4, -3, -1]
[14, 5, 3, 8, 15, 7, 4, 19, 12, 0, 2, 18, 6, 11, 13, 1, 17, 16, 10, 9] -> [3, 5, 14, 8, 4, 7, 15, 0, 12, 19, 2, 6, 18, 11, 1, 13, 9, 10, 16, 17]

Puntuación

Este es el código de golf , por lo que gana el código más corto en bytes.

JavaScript (ES6), 64 bytes

f=([n,...a],z=[],q=[n,...z])=>a+a?n<a[0]?[...q,...f(a)]:f(a,q):q

Recursion FTW! El algoritmo básico en uso aquí es realizar un seguimiento de la ejecución actual no ascendente en una matriz, "devolviéndola" cada vez que se encuentra un elemento ascendente. Hacemos esto de forma recursiva, continuamente concatenando los resultados, hasta que nos quedemos sin elementos. Al crear cada ejecución en reversa (en [n,...z]lugar de [...z,n]), podemos evitar la larga .reverse()sin costo.

Fragmento de prueba

f=([n,...a],z=[],q=[n,...z])=>a+a?n<a[0]?[...q,...f(a)]:f(a,q):q

g=a=>console.log("Input:",`[${a}]`,"Output:",`[${f(a)}]`)

g([1])
g([1,1])
g([1,2])
g([2,1])
g([3,2,1])
g([3,1,2])
g([3,1,1,2])
g([5,2,7,6,4,1,3])

<input id=I value="5, 2, 7, 6, 4, 1, 3">
<button onclick="g((I.value.match(/\d+/g)||[]).map(Number))">Run</button>

Python 3 , 63 bytes

f=lambda x,*p:x[:1]>p>()and p+f(x)or x and f(x[1:],x[0],*p)or p

Pruébalo en línea!

Jalea , 8 bytes

Ṁ;<œṗ³UF

Pruébalo en línea!

Explicación:

Ṁ;         Prepend the list [a1, a2… an] with its maximum.
  <        Elementwise compare this with the original list:
           [max(a) < a1, a1 < a2, …, a(n-1) < an, an]
           The first element is always 0.
   œṗ³     Partition the original list (³) at the indices
           of the non-zero values in the working list.
           (The spurious `an` at the end of the left argument,
           resulting from comparing lists of different sizes,
           is ignored by this operation, thankfully.)
      U    Reverse each part.
       F   Flatten.

JavaScript (ES6), 70 bytes

Claro, esto ya está superado por la respuesta de ETHproductions , pero eso es lo mejor que se me ocurrió hasta ahora sin usar la recursividad.

a=>a.map((n,i)=>a[x=[...o,...r=[n,...r]],i+1]>n&&(o=x,r=[]),r=o=[])&&x

Nota: Inicializar ambos ry ocon el mismo objeto exacto r = o = []puede parecer una idea peligrosa. Pero es seguro hacerlo aquí porque rse le asigna inmediatamente su propia instancia (que contiene el primer elemento de a) en la primera iteración con r = [n, ...r].

Casos de prueba

let f =

a=>a.map((n,i)=>a[x=[...o,...r=[n,...r]],i+1]>n&&(o=x,r=[]),r=o=[])&&x

console.log(JSON.stringify(f([1])));
console.log(JSON.stringify(f([1, 1])));
console.log(JSON.stringify(f([1, 2])));
console.log(JSON.stringify(f([2, 1])));
console.log(JSON.stringify(f([2, 3, 1])));
console.log(JSON.stringify(f([2, 1, 3])));
console.log(JSON.stringify(f([2, 1, 2])));
console.log(JSON.stringify(f([2, 1, 1])));
console.log(JSON.stringify(f([3, 1, 1, 2])));
console.log(JSON.stringify(f([3, 2, 1, 2])));
console.log(JSON.stringify(f([3, 1, 2, 2])));
console.log(JSON.stringify(f([1, 3, 2, 2])));
console.log(JSON.stringify(f([1, 0, 5, -234])));
console.log(JSON.stringify(f([1, 0, 1, 0, 1])));
console.log(JSON.stringify(f([1, 2, 3, 4, 5])));
console.log(JSON.stringify(f([5, 4, 3, 2, 1])));
console.log(JSON.stringify(f([2, 1, 5, 4, 3])));
console.log(JSON.stringify(f([2, 3, 1, 5, 4])));
console.log(JSON.stringify(f([5, 1, 4, 2, 3])));
console.log(JSON.stringify(f([5, 2, 7, 6, 4, 1, 3])));
console.log(JSON.stringify(f([-5, -2, -7, -6, -4, -1, -3])));
console.log(JSON.stringify(f([14, 5, 3, 8, 15, 7, 4, 19, 12, 0, 2, 18, 6, 11, 13, 1, 17, 16, 10, 9])));

MATL , 15 bytes

lidO>vYsGhXSOZ)

La entrada es un vector de columna, con el formato [5; 2; 7; 6; 4; 1; 3](punto y coma es el separador de fila).

Pruébalo en línea!

Tome la entrada [5; 2; 7; 6; 4; 1; 3]como un ejemplo.

Explicación

l     % Push 1
      % STACK: 1
i     % Push input
      % STACK: 1, [5; 2; 7; 6; 4; 1; 3]
d     % Consecutive differences
      % STACK: 1, [-3; 5; -1; -2; -3; 2]
O>    % Test if greater than 0, element-wise
      % STACK: 1, [0; 1; 0; 0; 0; 1]
v     % Concatenate vertically
      % STACK: [1; 0; 1; 0; 0; 0; 1]
Ys    % Cumulative sum
      % STACK: [1; 1; 2; 2; 2; 2; 3]
G     % Push input again
      % STACK: [1; 1; 2; 2; 2; 2; 3], [5; 2; 7; 6; 4; 1; 3]
h     % Concatenate horizontally
      % STACK: [1 5; 1 2; 2 7; 2 6; 2 4; 2 1; 3 3]
XS    % Sort rows in lexicographical order
      % STACK: [1 2; 1 5; 2 1; 2 4; 2 6; 2 7; 3 3]
OZ)   % Get last column. Implicitly display
      % STACK: [2; 5; 1; 4; 6; 7; 3]

Mathematica, 30 27 bytes

^{3 bytes guardados debido a @Martin Ender .}

Join@@Sort/@Split[#,#>#2&]&

Función anónima. Toma una lista de números como entrada y devuelve una lista de números como salida.

Python 2, 100 bytes

Un golf realmente terrible, pero quería publicar mi solución (uno no solo supera a Dennis) ...

d=input();L=[];x=0;d+=-~d[-1],
for i in range(1,len(d)):
 if d[i]>d[i-1]:L+=d[x:i][::-1];x=i
print L

Prueba en repl.it!

La entrada debe darse como un literal de lista de Python, como [5, 3, 4, 2, 6, 1].

La idea básica es hacer un uso intensivo de la sintaxis de corte de Python, cortando cada sección necesaria de la matriz, invirtiéndola y agregándola a la nueva matriz.

Pyke, 11 8 bytes ( versión anterior )

$0m<fm_s

Pruébalo aquí! (funciona en la última versión)

$        -     delta(input)
 0m<     -    map(i<0 for i in ^)
    f    -   split_at(input, ^)
     m_  -  map(reverse, ^)
       s - sum(^)

Retina , 163 bytes

Sí, sé lo horrible que es esto. Apoyar ceros y negativos fue muy divertido. El recuento de bytes asume la codificación ISO 8859-1.

\d+
$*
(?<=-1*)1
x
-

x,1
x¶1
\b(1+),(1+\1)\b
$1¶$2
,,1
,¶1
x,(¶|$)
x¶¶
(?<=\b\1x+(?=,(x+))),\b
¶
O%$#`.(?=(.*))
$.1
+`¶
,
\bx
-x
(\w+)
$.1
^,
0,
,$
,0
,,
,0,
^$
0

Pruébalo en línea

Explicación:

\d+                         # Convert to unary
$*
(?<=-1*)1                   # Replace negatives with x's instead of 1's
x
-                           # Remove minus sign

x,1                         # Separate if negative before positive
x¶1
\b(1+),(1+\1)\b             # or greater positive follows a positive
$1¶$2
,,1                         # or positive follows a zero
,¶1
x,(¶|$)                     # or zero follows a negative
x¶¶
(?<=\b\1x+(?=,(x+))),\b     # or negative follows a negative of greater magnitude.
¶
O%$#`.(?=(.*))              # Swear at the input, then reverse each line
$.1
+`¶                         # Remove breaks, putting commas back
,
\bx                         # Put the minus signs back
-x
(\w+)                       # Replace unary with length of match (decimal)
$.1
^,                          # Do a bunch of replacements to resurrect lost zeros
0,
,$
,0
,,
,0,
^$
0

05AB1E , 19 18 16 14 bytes

Guardado 2 bytes usando el truco de clasificación de Luis Mendo

ü‹X¸ì.pO¹)ø{ø¤

Pruébalo en línea!

Explicación

Entrada de ejemplo [5, 2, 7, 6, 4, 1, 3]

ü‹               # pair-wise less-than
                 # STACK: [0, 1, 0, 0, 0, 1]
  X¸ì            # prepend a 1
                 # STACK: [1, 0, 1, 0, 0, 0, 1]
     .p          # prefixes
       O         # sum
                 # STACK: [1, 1, 2, 2, 2, 2, 3]
        ¹        # push input
                 # STACK: [1, 1, 2, 2, 2, 2, 3], [5, 2, 7, 6, 4, 1, 3]
         )       # wrap stack in list
                 # STACK: [[1, 1, 2, 2, 2, 2, 3], [5, 2, 7, 6, 4, 1, 3]]
          ø      # zip
                 # STACK: [[1, 5], [1, 2], [2, 7], [2, 6], [2, 4], [2, 1], [3, 3]]
           {     # sort
                 # STACK: [[1, 2], [1, 5], [2, 1], [2, 4], [2, 6], [2, 7], [3, 3]]
            ø    # zip
                 # STACK: [[1, 1, 2, 2, 2, 2, 3], [2, 5, 1, 4, 6, 7, 3]]
             ¤   # tail
                 # OUTPUT: [2, 5, 1, 4, 6, 7, 3]

Solución anterior de 16 bytes

Dü‹X¸ì.pO.¡€g£í˜

JavaScript (ECMA 6), 121 128 125 119 108 bytes

f=a=>{p=a[0],c=[],b=[];for(e of a){e>p&&b.push(c.reverse(c=[]));c.push(p=e)}return[].concat.call([],...b,c)}

Expresión Lambda toma un único Arrayparámetro, a.

Gracias a @ETHproductions por ayudarme a ver mi primer error.

Ruby, 60 55 bytes

s=->x{x.slice_when{|p,q|p<q}.map{|z|z.reverse}.flatten} 

Más o menos lo que pidió el desafío. He definido una lambda s, que toma una matriz x, y Sever (rodajas) en pedazos más pequeños, donde el elemento siguiente sería mayor que. Esto devuelve un enumerador, al que podemos llamar map e invertir el orden de las piezas, antes de finalmente juntarlo todo con flatten, que concatena los elementos en el orden definido en una matriz.

Pruebas

p s[[1]]===[1]
p s[[1, 1]]===[1, 1]
p s[[1, 2]]===[1, 2]
p s[[2, 1]]===[1, 2]
p s[[2, 3, 1]]===[2, 1, 3]
p s[[2, 1, 3]]===[1, 2, 3]
p s[[2, 1, 2]]===[1, 2, 2]
p s[[2, 1, 1]]===[1, 1, 2]
p s[[3, 1, 1, 2]]===[1, 1, 3, 2]
p s[[3, 2, 1, 2]]===[1, 2, 3, 2]
p s[[3, 1, 2, 2]]===[1, 3, 2, 2]
p s[[1, 3, 2, 2]]===[1, 2, 2, 3]
p s[[1, 0, 5, -234]]===[0, 1, -234, 5]
p s[[1, 0, 1, 0, 1]]===[0, 1, 0, 1, 1]
p s[[1, 2, 3, 4, 5]]===[1, 2, 3, 4, 5]
p s[[5, 4, 3, 2, 1]]===[1, 2, 3, 4, 5]
p s[[2, 1, 5, 4, 3]]===[1, 2, 3, 4, 5]
p s[[2, 3, 1, 5, 4]]===[2, 1, 3, 4, 5]
p s[[5, 1, 4, 2, 3]]===[1, 5, 2, 4, 3]
p s[[5, 2, 7, 6, 4, 1, 3]]===[2, 5, 1, 4, 6, 7, 3]
p s[[-5, -2, -7, -6, -4, -1, -3]]===[-5, -7, -2, -6, -4, -3, -1]
p s[[14, 5, 3, 8, 15, 7, 4, 19, 12, 0, 2, 18, 6, 11, 13, 1, 17, 16, 10, 9]]===[3, 5, 14, 8, 4, 7, 15, 0, 12, 19, 2, 6, 18, 11, 1, 13, 9, 10, 16, 17]

Brachylog , 10 bytes

~c:{>=r}ac

Pruébalo en línea!

Explicación

~c            Deconcatenate the Input
  :{>=r}a     Each resulting sublist must be non-increasing, and then reverse it
         c    Concatenate

Dyalog APL , 7 15 bytes

Requiere ⎕ML←3, que es el predeterminado en muchos sistemas. *

{∊⌽¨⍵⊂⍨1+⍵-⌊/⍵}

∊ alistarse (aplanar)

⌽¨ cada uno invertido

⍵⊂⍨ el argumento particionado * cortando donde cada elemento correspondiente es más grande que su predecesor en

1+ uno más

⍵- el argumento menos

⌊/⍵ el elemento más pequeño del argumento

La antigua solución de 7 bytes falla con enteros no positivos:

Requiere ⎕ML←3, que es el predeterminado en muchos sistemas. *

∊⌽¨⊆⍨⎕

∊ alistar (aplanar) el

⌽¨ cada uno invertido

⊂⍨ autoparticionado *

* Partition ( ⊂) es una función que corta su argumento derecho donde el argumento izquierdo correspondiente es más grande que el anterior. (Desafortunadamente, solo acepta enteros no negativos, y cero tiene un significado especial.) A partir de la versión 16, esta funcionalidad ⊂está disponible en todos los sistemas (incluso aquellos donde ⎕ML≠3), utilizando el glifo ⊆.

Haskell, 49 bytes

(a:b)%l|any(<a)l=l++b%[a]|1<2=b%(a:l)
_%l=l
(%[])

Ejemplo de uso: (%[]) [5,2,7,6,4,1,3]-> [2,5,1,4,6,7,3].

Enfoque recursivo. La función %toma la lista de entrada como su primer parámetro y un acumulador lque realiza un seguimiento del fragmento no ascendente hasta ahora (en orden inverso). El caso base se alcanza cuando la lista de entrada está vacía y luego el resultado es el acumulador. Si la lista de entrada no está vacía y el primer elemento ano cabe en el fragmento actual ( any(<a)l), devuelva el acumulador y agregue una llamada recursiva en el resto de la lista y acomo el nuevo acumulador ( l++b%[a]). De lo contrario, haga una llamada recursiva en el resto de la lista y aanteponga al acumulador ( b%(a:l)). La función principal (%[])llama %con un acumulador vacío.

Retina , 98 bytes

El recuento de bytes asume la codificación ISO 8859-1.

$

-(\d+)
$1$*-/
\d+
$*
S-`(?<=(-+)/ )(?!\1)|(?=\b(1+))(?<!\2 )
O%`\S* 
¶

((-)|1)*/? 
$2$#1 
 $

Pruébalo en línea!

R, 64 bytes

cat(unlist(lapply(split(x<-scan(),cumsum(c(F,diff(x)>0))),rev)))

Lee la entrada de stdin. Dividimos la entrada en una lista de vectores usando lo split()que requiere una variable de factor que agrupa la entrada. El factor se crea tomando la suma acumulativa del vector lógico para el cual la diferencia es positiva.

Considere el vector:

x=c(5, 2, 7, 6, 4, 1, 3)

Ahora, tomar la diferencia y anteponer Fejecutando y=c(F,diff(x)>0)produciría el siguiente vector lógico:

[1] FALSE FALSE  TRUE FALSE FALSE FALSE  TRUE

Tomar la suma acumulativa cumsum(y)produce un vector donde cada grupo está representado por un factor único sobre el cual podemos combinar con la splitfunción:

[1] 0 0 1 1 1 1 2

Octava, 75 44 bytes

Basado en la respuesta MATL de @LuisMendo

@(a)sortrows([cumsum([1;diff(a)>0]),a])(:,2)

Pruébalo en línea!

Respuesta anterior

@(a)[fliplr(mat2cell(f=fliplr(a),1,diff(find([1,diff(f)<0,numel(a)])))){:}]

Pruébalo en línea!

invertir la matriz

f=fliplr(a)

tomar primera diferencia de f

d = diff(f);

encontrar la posición de donde el siguiente elemento es menor que el elemento anterior

p=find([1,diff(f)<0,numel(a)])

la primera diferencia de las posiciones devuelve la longitud de cada submatriz

len=diff(p)

use la longitud de cada subconjunto mat2cellpara dividir el conjunto en una lista anidada de conjuntos

nest = mat2cell(f,1,len);

invertir la lista anidada

rev_nest = fliplr(nest) 

aplanar la lista anidada

[rev_nest{:}]

Pyth - 15 bytes

s_McQf<@QtT@QTU

Pruébelo en línea aquí .

Perl 6 , 59 bytes

{map |+«*.[0].reverse,m/:s([(\-?\d+)<?{[>=] $0}>] +)+/[0]}

Solución basada en expresiones regulares.
¡Porque esta es Sparta Perl!

• m/ /: Stringify la matriz de entrada, y hacer coincidir una expresión regular contra ella.
• (\-? \d+): Unir un número y capturarlo como $0.
• <?{ [>=] $0 }>: Aserción de ancho cero que solo coincide si todos los $0capturados hasta el momento en la coincidencia actual están en orden no ascendente.
• ([ ] +)+: Repita los dos últimos pasos tan a menudo como sea posible, de lo contrario, comience una nueva sub-partida
• map , [0]: Iterar sobre los sub-partidos.
• |+«*.[0].reverse: Para cada uno, tome la lista de valores coincidentes $0, inviértala, coaccione los valores a números ( +«) y deslícelos en la lista externa ( |).

Perl 6 , 63 bytes

sub f(\a){flat $_,f a[+$_..*]with first {[<=] $_},:end,[\R,] a}

Solución de procesamiento de listas recursivas.
Más laborioso de lo que esperaba.
Aunque el lenguaje tiene muchas funciones integradas convenientes, parece que no hay ninguna para la partición de listas (por ejemplo, como las de Ruby slice_wheno Haskell takeWhile).

Apilado , no competitivo, 34 bytes

Aún desarrollando constantemente este lenguaje.

{e.b:e b last<}chunkby$revmap flat

El argumento se basa en TOS. Pruébalo aquí!

chunkbytoma una función y recopila matrices de datos contiguos que satisfacen la función. La función entonces es:

{e.b:e b last<}
{e.b:         }  function with arguments [e, <unused>, b]--the element, <the index>, and the
                 chunk being built
     e       <   check if e is less than
       b last    the last element of b

Esto da una matriz estrictamente decreciente.

$revmapes básicamente [rev]mapy revierte cada elemento.

flat finalmente aplana la matriz.

Un poco de diversión para realmente ordenar la matriz:

[{e.b:e b last<}chunkby$revmap flat] @:sortstep
[$sortstep periodloop] @:sort

10:> @arr
arr out
arr shuf @arr
arr out
arr sort out

Esto genera (por ejemplo):

(0 1 2 3 4 5 6 7 8 9)
(4 5 1 0 6 7 2 8 9 3)
(0 1 2 3 4 5 6 7 8 9)

Python, 151 139 Bytes

¡Guardado 12 bytes gracias a @ Flp.Tkc!

En ninguna parte cerca de @ Flp.Tkc, y mucho menos ...

def s(l):
 r=[];i=j=0
 while j<len(l)-1:
  if l[j+1]>l[j]:r+=l[i:j+1][::-1],;i=j+1
  j+=1
 r+=l[i:j+1][::-1],;return[i for s in r for i in s]

Python 2, 74 bytes

b=[];c=[];a+=9e9,
for i in a[:-1]:
 b=[a.pop(0)]+b
 if b[0]<a[0]:c+=b;b=[]

Entrada a, salida enc

Python 3, 191 bytes

a=[int(i)for i in input().split()]
while a!=sorted(a):
 b=[[]]
 for i,j in enumerate(a):
  if a[i-1]<j:b+=[[j]]
  else:b[-1]+=[j]
 a=[]
 for l in[k[::-1]for k in b]:a+=[k for k in l]
print(a)

No estoy seguro de si sortedestá permitido usar la función para verificar aquí, pero no se me ocurre una buena razón para ello, y redujo mi recuento de bytes en ~ 30 bytes.

Clojure, 105 bytes

#(filter number?(mapcat reverse(partition-by not(mapcat(fn[[a b]][a(< b a)])(partition 2 1(conj % 1))))))

Particiones en pares de números consecutivos, pone trueo falseentre ellos, particiones en notque truey los números se hacen falsey false true, invierte particiones y mantiene los valores numéricos.