Un algoritmo de "clasificación"

33

Hay un "algoritmo de ordenamiento", a veces llamado ordenamiento de Stalin, en el cual, para ordenar una lista, simplemente elimina elementos de la lista hasta que se ordena en orden creciente. Por ejemplo la lista

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

Cuando "ordenado" con Stalin se convierte en ordenar

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

Los tres fueron retirados porque estaba fuera de servicio.

Ahora, obviamente, hay muchas formas de eliminar elementos para ordenar una lista. Por ejemplo, cualquier lista con menos de dos elementos debe ordenarse, de modo que simplemente eliminando suficientes elementos a ciegas siempre podemos ordenar una lista. Dado que este es el caso, solo nos importa el resultado más largo posible de un tipo de Stalin.

Su tarea será tomar una lista de enteros positivos y generar la longitud de la lista ordenada (creciente) más larga a la que se puede llegar eliminando elementos de la lista original. Es decir, encontrar la longitud de la sublista ordenada más larga (posiblemente no contigua).

Las listas ordenadas pueden tener el mismo elemento más de una vez seguidas. No necesita admitir la lista vacía a menos que su programa esté vacío.

Tanteo

Su respuesta se puntuará según la longitud de su propio tipo de Stalin más largo posible. Los programas se interpretarán como una secuencia de bytes en lugar de caracteres, y su orden será el natural que surge al interpretar los bytes como números. Los puntajes más bajos son mejores.

Esto no es

Aquí hay una herramienta ordenada para ayudarlo a calificar sus respuestas.

Casos de prueba

[1, 2, 4, 5, 3, 6, 6] -> 6
[19, 2] -> 1
[3, 3, 4, 3] -> 3
[10] -> 1
[1, 2, 4, 9] -> 4
[1, 90, 2, 3, 4, 5] -> 5
[1, 90, 91, 2, 3, 4, 5] -> 5
Asistente de trigo
fuente
3
En resumen: muestra la longitud de la secuencia creciente más larga (no estrictamente) .
usuario202729
1
Me gusta la regla "No necesita admitir la lista vacía a menos que su programa esté vacío".
Paŭlo Ebermann el
Este desafío me recuerda mucho al desafío de dropsort
Stefnotch
1
Hice un corrector en ptpb.pw/SVSt.html . Todavía no es muy funcional, pero funciona. (TODO: * gráfico de barras * partición en secuencias menos decrecientes * soporte para otras páginas de códigos)
usuario202729
@ user202729 ¡Genial! Lo he agregado a la publicación. Siéntase libre de editar versiones más nuevas si es necesario.
Wheat Wizard

Respuestas:

8

Pitón 2 , longitud 14 12 10 9

M=max;X=exit;i=input();L=[0]*M(i)
for	a	in	i:L[a-1]=M(L[:a])+1
X(M(L))

La salida es a través del código de salida.

Pruébalo en línea!

Cómo funciona

LL[a1]a

L

a[L[0],,L[a1]]aaaL[a1]

L

Dennis
fuente
¿Puedes explicar por qué funciona? Estoy teniendo momentos difíciles para comprenderlo :(
Dead Possum
He añadido una explicación.
Dennis
5

Haskell , puntaje 8 7, 48 bytes

(l:k)%d|d>l=k%d|3>2=max(1+k%l)(k%d)
c%b=0
a=(%0)

Pruébalo en línea!

La sublista ordenada más larga es

%%%%%%)
Asistente de trigo
fuente
4

Gelatina , longitud  4  2

ṢƑƇZLƲ}ŒP

Pruébalo en línea!

Bytes en la página de códigos de Jelly

183 146 144 90 76 169 125 19 80

Cómo funciona

ṢƑƇZLƲ}ŒP  Main link. Argument: A (array)

       ŒP  Powerset; yield P, the array of all sub-arrays of A.
     Ʋ     Vier; combine the preceding four links into a monadic chain...
      }    and apply the chain to the right argument (P).
  Ƈ            Comb; only keep arrays for which the link to the left returns 1.
ṢƑ             Sort fixed; yield 1 if sorting doesn't alter the array.
   Z           Zip; read the filtered powerset by columns.
    L          Take the length.
Dennis
fuente
3

Pyth, puntaje 3 2 ( 7 bytes)

leSI#y

Ahorré un punto gracias a Anders Kaseorg.
Pruébalo aquí

Explicación

leSI#y
     yQ    Take the power set of the (implicit) input (preserving order).
  SI#      Get the ones that are sorted.
 e         Take the last (longest).
l          Get the length.

fuente
leSI#ypuntuaciones 2.
Anders Kaseorg
2

Stax , 4 clasificaciones stalin de longitud máxima

S{:^fF%|M

Ejecutar y depurarlo

Funciona así.

S       powerset of input
{:^f    filter by non-descending sequences
F%|M    take the maximum length remaining
recursivo
fuente
2

R , puntaje 15 11, 72 62 bytes

function(L,M=max,A=1:M(L)*0){for(Y in L)A[Y]=M(A[1:Y])+1;M(A)}

Pruébalo en línea!

La respuesta de Python de Ports Dennis a R.

Giuseppe
fuente
Solo cambiar nombres de variables no ayudará, porque como muestra su último enlace, ninguno de ellos se usa en la subcadena (encontrada) que da puntaje 15.
Ørjan Johansen
@ ØrjanJohansen ah, por supuesto, soy bastante tonto. Supongo que otro enfoque es necesario.
Giuseppe
2

Brachylog , longitud 2 (4 bytes)

⊇≤₁l

Pruébalo en línea!

Una respuesta que compensa ser tan conciso al no ser tan corto ordenado.

( 08 03 80 6Cen la página de códigos de Brachylog)

        Output
   l    the length of
 ≤₁     a non-decreasing
⊇       sublist of
        the input.
        (maximizing the size of the sublist)
Cadena no relacionada
fuente
Se me ocurrió ►LSnmOṖHusk, pero su puntaje (al menos para su longitud) es demasiado malo para molestarse en publicar ...
Cadena no relacionada