Implemente la "clasificación perezosa"

44

Se supone que debo ordenar una lista de números, pero soy muy vago. Es realmente difícil imaginar cómo intercambiar todos los números hasta que todos estén en orden creciente, por lo que se me ocurrió mi propio algoritmo que garantizará que la nueva lista esté ordenada¹. Así es como funciona:

Para una lista de tamaño N , necesitaremos iteraciones N-1 . En cada iteración,

  • Compruebe si el número N es el más pequeño que el número N + 1 . Si es así, estos dos números ya están ordenados y podemos omitir esta iteración.

  • Si no lo están, debe disminuir continuamente los primeros N números hasta que estos dos números estén en orden.

Tomemos un ejemplo concreto. Digamos que la entrada fue

10 5 7 6 1

En la primera iteración, compararemos 10 y 5. 10 es mayor que 5, por lo que lo disminuimos hasta que sea más pequeño:

4 5 7 6 1

Ahora comparamos 5 y 7. 5 es más pequeño que 7, por lo que no necesitamos hacer nada en esta iteración. Así que vamos al siguiente y comparamos 7 y 6. 7 es mayor que 6, por lo que disminuimos los primeros tres números hasta que sea menor que 6, y obtenemos esto:

2 3 5 6 1

Ahora comparamos 6 y 1. Nuevamente, 6 es mayor que 1, por lo que disminuimos los primeros cuatro números hasta que sea menor que 1, y obtenemos esto:

-4 -3 -1 0 1

¡Y hemos terminado! Ahora nuestra lista está en perfecto orden. Y, para mejorar aún más las cosas, solo tuvimos que recorrer la lista N-1 veces, por lo que este algoritmo ordena las listas en el tiempo O (N-1) , lo cual estoy bastante seguro de que es el algoritmo más rápido que existe.²

Su desafío para hoy es implementar este Lazy Sort. Su programa o función recibirá una serie de enteros en el formato estándar que desee, y debe realizar esta clasificación diferida y devolver la nueva lista "ordenada" . La matriz nunca estará vacía o contendrá no enteros.

Aquí hay unos ejemplos:

Input: 10 5 7 6 1
Output: -4 -3 -1 0 1

Input: 3 2 1
Output: -1 0 1

Input: 1 2 3
Output: 1 2 3

Input: 19
Output: 19

Input: 1 1 1 1 1 1 1 1 1 
Output: -7 -6 -5 -4 -3 -2 -1 0 1 

Input: 5 7 11 6 16 2 9 16 6 16
Output: -27 -25 -21 -20 -10 -9 -2 5 6 16

Input: -8 17 9 7
Output: -20 5 6 7

Como siempre, este es el , ¡así que escribe el programa más corto que puedas!


¹ Esto no significa lo que parece, pero es técnicamente cierto

² Estoy completamente bromeando, por favor no me odies

DJMcMayhem
fuente
66
Creo que no eres flojo si lo haces de esta manera
Jörg Hülsermann
44
@ JörgHülsermann, bueno, algunos enteros son demasiado pesados ​​... no están exactamente de humor para soportar tanto peso, es mejor quitarse solo las cosas más importantes
Erik the Outgolfer
21
<sarcasm>En realidad, este algoritmo de clasificación sigue O(N^2)registrando complejidad en el tiempo porque tiene que pasar por todos los elementos a los que se accedió anteriormente en la lista para disminuirlos. Recomiendo revisar la lista al revés y disminuir solo un número por paso según sea necesario. ¡Esto te dará verdadera O(N)complejidad! </sarcasm>
Value Ink
1
@ValueInk O(n^2)en términos de accesos a la memoria, pero ¿no es O(n)para hacer comparaciones?
Cole Johnson
77
@ColeJohnson técnicamente sí, pero la complejidad del tiempo debe tener en cuenta todos los pasos del algoritmo. Todavía tiene que recorrer todos los índices anteriores en cada iteración, por lo que aún sale O(N^2).
Value Ink

Respuestas:

12

Jalea ,  14 12 11  9 bytes

-2 bytes gracias a ETHproductions (use la diada mínima, «)

I’«0Ṛ+\Ṛ+

Un enlace monádico que toma y devuelve listas de enteros.

Pruébalo en línea! o ver el conjunto de pruebas .

¡Realmente no creo que esto sea suficiente Lazy ™!

¿Cómo?

I’«0Ṛ+\Ṛ+ - Link: list of integers, a              e.g. [ 8, 3, 3, 4, 6, 2]
I         - increments between consecutive items of a   [-5, 0, 1, 2,-4 ]
 ’        - decrement (vectorises)                      [-6,-1, 0, 1,-5 ]
   0      - literal 0
  «       - minimum of decremented increments and zero  [-6,-1, 0, 0,-5 ]
    Ṛ     - reverse                                     [-5, 0, 0,-1,-6 ]
      \   - cumulative reduce with:
     +    -   addition                                  [-5,-5,-5,-6,-12]
       Ṛ  - reverse                                     [-12,-6,-5,-5,-5]
        + - addition (with a)                           [-4,-3,-2,-1, 1, 2]
Jonathan Allan
fuente
12

Haskell , 40 bytes

f(a:r)|h:t<-f r=h-max(r!!0-a)1:h:t
f x=x

Pruébalo en línea!

xnor
fuente
11
Un lenguaje perezoso parece apropiado para este desafío
tomsmeding
8

JavaScript (ES6), 61 bytes

a=>a.map((b,i)=>a=(b-=a[i+1])>0?a.map(c=>i--<0?c:c-b-1):a)&&a

Casos de prueba

Arnauld
fuente
7

Jalea , 12 bytes

I»1U
0ị;Ç_\U

Pruébalo en línea!

Cómo funciona

I»1U  Helper link. Argument: l (list of integers)
I     Compute the increments (difference between items) of l.
 »1   For each item n, take the maximum of n and 1.
   U  Reverse.

0ị;Ç_\U  Main link. Argument: l (list of integers)
   Ç     Call the helper link with argument l.
  ;      Concatenate this with
0ị       the 0th last item of the (1-indexed) l. (Can't use Ṫ because it modifies l)
    _\   Cumulatively reduce the result by subtraction.
      U  Reverse.

La idea básica en juego es esta: si invierte las matrices de entrada y salida, la salida es simplemente la entrada con cada delta de 0 o mayor reemplazado por -1. Por ejemplo:

[10,  5,  7,  6,  1]   input
[ 1,  6,  7,  5, 10]   reverse
[   5,  1, -2,  5  ]   deltas
[  -1, -1, -2, -1  ]   min(deltas, -1)
[ 1, -1, -2, -1, -1]   reverse and concat the last item of the original
[ 1,  0, -2, -3, -4]   re-apply deltas
[-4, -3, -2,  0,  1]   reverse
ETHproducciones
fuente
5

k, 20 bytes

{x-|+\0,1_0|1+-':|x}

Pruébalo en línea.

Explicación:

{                  } /function, x is input
                 |x  /reverse x
              -':    /difference between every element
            1+       /add one to each difference
          0|         /make minimum difference be 0
      0,1_           /swap first difference with a 0
    +\               /cumulative sum
   |                 /reverse again
 x-                  /subtract from x
zgrep
fuente
4

Haskell, 56 bytes

a#(x:y:z)=map(+min(y-x-1)0)(a++[x])#(y:z)
a#x=a++x
([]#)

Pruébalo en línea!

Mantenga la primera parte de la lista en el parámetro a. En cada paso, agregue el siguiente elemento xal final de ay aumente todos los elementos de a por el mínimo de (y-x-1)y 0.

nimi
fuente
4

Python , 54 bytes

f=lambda a,*r:r and[f(*r)[0]-max(r[0]-a,1)]+f(*r)or[a]

Pruébalo en línea!

Toma entrada salpicada como f(1,2,3). Emite una lista. Utiliza tiempo exponencial.

xnor
fuente
3

C #, 76 bytes

a=>{for(int d=0,i=a.Length-1;i>0;a[--i]-=d)d=a[i-1]-d<a[i]?d:a[i-1]-a[i]+1;}

Esto modifica la lista en su lugar. Revisa la lista al revés y mantiene un total acumulado del delta para aplicar a cada número.

Hand-E-Food
fuente
2

JavaScript (ES6), 59 bytes

f=([n,...a],p=a[0]-n)=>a+a?[(a=f(a))[0]-(p>1?p:1),...a]:[n]
ETHproducciones
fuente
Guau. Estaba a punto de escribir una solución JS, pero luego vi esto. No pensé en usar el operador de propagación así en los parámetros
andrewarchi
Puede dejar las f=respuestas de JS para guardar dos bytes
andrewarchi
@andrewarchi Gracias, pero esta función en particular debe llamarse a sí misma ( f(a)), por lo que aún requiere el nombre.
ETHproductions
Olvidé que era recursivo
andrewarchi
2

Brain-Flak , 153 bytes

{(({})<>[({})])(({}({}))[({}[{}])])<>(([{}]({})))([({}<(())>)](<>)){({}())<>}{}{((<{}>))<>{}}{}<>{}{{}({}<>{}())((<>))}{}{}}{}<>{}([]){{}({}<>)<>([])}<>

Pruébalo en línea!

Esto incluye +1para la -rbandera.

#While True
{

    #Push the last value left in the array minus the counter onto the alternate stack
    (({})<>[({})])

    #Put the counter back on top of the alternate stack
    (({}({}))[({}[{}])])

    #Toggle
    <>

    #Find the difference between the last two inputs left on the array
    (([{}]({})))

    #Greater than or equal to 0?
    ([({}<(())>)](<>)){({}())<>}{}{((<{}>))<>{}}{}<>{}

    #If So:
    {

      #Pop the truthy/falsy value
      {}

      #Increment the counter by the difference between elements +1
      ({}<>{}())

      #Push two falsys
      ((<>))

    #Endwhile
    }

    #Pop the two falsys
    {}{}

#Endwhile
}

#Pop the falsy

{}

#Toggle back
<>

#Pop the counter

#Reverse the stack
{}
([]){{}({}<>)<>([])}<>
DJMcMayhem
fuente
2

R, 56 bytes

function(s){s-c(rev(cumsum(rev(pmax(0,-diff(s)+1)))),0)}

aPaulT
fuente
1
buen uso de diff, estaba tratando de descubrir cómo hacer que eso funcione ... Por cierto, puedes deshacerte de las llaves alrededor del cuerpo de la función durante -2 bytes, pero mejor aún, puedes usar en s=scan()lugar de una función definición para guardar algunos bytes más. Sería genial si incluyera un enlace para Probar en línea para que otras personas puedan verificar que este código funciona para todos los casos de prueba.
Giuseppe
¡Sin preocupaciones! todos comenzamos en alguna parte :)
Giuseppe
1

JavaScript (ES6), 68 bytes

a=>a.map((v,i)=>(d=v-o[i+1]+1)>1?o=o.map((v,j)=>j>i?v:v-d):0,o=a)&&o

Entrada y salida es una matriz de enteros.

Fragmento de prueba

f=
a=>a.map((v,i)=>(d=v-o[i+1]+1)>1?o=o.map((v,j)=>j>i?v:v-d):0,o=a)&&o
<input id=I oninput="O.value=f(this.value.split` `.map(x=>+x)).join` `">
<input id=O disabled>

Justin Mariner
fuente
1

JavaScript (ES6), 50 bytes

f=a=>(b=[...a]).some((_,i)=>a[i]-->=a[i+1])?f(a):b

Explicación:

Esta es una solución recursiva, que primero clona la matriz, luego disminuye todos los valores hasta que un elemento sea mayor o igual al siguiente elemento en la matriz.

La función se llama a sí misma siempre que algún elemento esté fuera de servicio. Cuando los elementos finalmente se ordenan, se devuelve el clon. (No podemos devolver la matriz en sí, porque el some()método habría disminuido todos sus elementos, haciéndolos desaparecer en -1).

Casos de prueba:

f=a=>(b=[...a]).some((_,i)=>a[i]-->=a[i+1])?f(a):b

console.log(f([10,5,7,6,1])+'');
console.log(f([1,1,1,1,1,1,1,1,1])+'');
console.log(f([5,7,11,6,16,2,9,16,6,16])+'');
console.log(f([19])+'');
console.log(f([-8,17,9,7])+'');
console.log(f([1,2,3,4,5,6,7])+'');

Rick Hitchcock
fuente
1

SWI-Prolog, 194 bytes

:-use_module(library(clpfd)).
f([],[],_,_).
f([A|B],[M|N],P,D):-A#=M-D-E,A#<P,abs(M,S),T#=S+1,E in 0..T,label([E]),f(B,N,A,D+E).
l([],[]).
l(A,B):-reverse(Z,B),f([X|Y],Z,X+1,0),reverse(A,[X|Y]).

Puede probarlo en línea aquí: http://swish.swi-prolog.org/p/LazySort.pl

Usted pregunta l(L, [10,5,7,6,1]).qué dice "resolver para L, donde L es la versión ordenada perezosa de esta lista".

Las dos funciones son:

  • lazysorted (A, B): indica que A es la versión lazysorted de B, si ambas son listas vacías, o si A se puede obtener invirtiendo B, llamando a una función auxiliar para recorrer la lista y restar con un acumulador empujando cada valor más bajo que el anterior e invirtiendo el resultado de eso de nuevo a la forma correcta.
  • fhelper coincide con dos listas, el valor del número anterior en la lista y un acumulador de diferencia variable, y resuelve que el nuevo valor de la posición actual de la lista sea el valor original menos el acumulador de diferencia, opcionalmente menos un nuevo valor requerido para forzar esto valor por debajo del número anterior en la lista, y fdebe resolver la cola de la lista de forma recursiva con el acumulador de diferencia ahora aumentado.

Captura de pantalla de los casos de prueba en Swish:

imagen que muestra los casos de prueba que se ejecutan en Swish

TessellatingHeckler
fuente
0

JavaScript (ES6), 61 bytes

a=>a.reduceRight((r,e)=>[e-(d=(c=e-r[0]+1)>d?c:d),...r],d=[])

No es la solución más corta, pero no pude dejar pasar la oportunidad de usar reduceRight.

Neil
fuente
0

C # (.NET Core) , 89 88 86 79 bytes

  • Guardado solo 1 byte con un enfoque ligeramente diferente.
  • Guardado otros 2 bytes con una simplificación del fors.
  • Ahorró 7 bytes gracias a las increíbles habilidades de golf de VisualMelon.
a=>{for(int i=0,j,k;++i<a.Length;)for(k=a[i-1]-a[j=i]+1;--j>=0;)a[j]-=k>0?k:0;}

Pruébalo en línea!

Primero foritera a través de la matriz, luego calcula el decremento y finalmente el segundo fordisminuye los elementos si es necesario hasta la iposición th.

¿Es válido simplemente modificar la matriz original en lugar de devolver una nueva (aún acostumbrarse a las reglas)?

Charlie
fuente
Sí, modificar la matriz original está perfectamente bien. :)
DJMcMayhem
44
@DJMcMayhem gracias, me sentí demasiado vago para crear uno nuevo. :)
Charlie