Orden de inserción inversa

19

Objetivo

Genere la lista codificada original, a partir de los movimientos que haría una Clasificación de inserción para ordenarla. La lista original tendrá todos los números desde 0hasta N-1(inclusive) donde Nestá el tamaño de la entrada.

Entrada

Una lista que contiene los movimientos necesarios para ordenar la lista. Cada valor representa la cantidad de ranuras desplazadas por el número original (codificado) para estar en su posición correcta, tenga en cuenta que este proceso es de izquierda a derecha.
El valor en la posición (indexada a 0) ien la lista de entrada estará entre 0e iinclusive.
No necesita manejar entradas inválidas, cualquier comportamiento es aceptable en este caso (bloqueo, bucle infinito, etc.).

Salida

La lista revuelta

Paso a paso para generar los movimientos.

Scrambled List | Moves to sort
[4,0,2,1,3,5]  | [0, , , , , ] #4 stay in place
[4,0,2,1,3,5]  | [0,1, , , , ] #0 is moved 1 slot to the left
[0,4,2,1,3,5]  | [0,1,1, , , ] #2 is moved 1 slot
[0,2,4,1,3,5]  | [0,1,1,2, , ] #1 is moved 2 slot
[0,1,2,4,3,5]  | [0,1,1,2,1, ] #3 is moved 1 slot
[0,1,2,3,4,5]  | [0,1,1,2,1,0] #5 is in the right place already
[0,1,2,3,4,5]

Entonces, para la entrada, [0,1,1,2,1,0]su programa necesita salir [4,0,2,1,3,5].
Tenga en cuenta que los movimientos no están en la posición en la lista ordenada (final), sino en el segmento ordenado (la sección en negrita)

Casos de prueba

[0,0,0] -> [0,1,2]
[0,1,0,1] -> [1,0,3,2]
[0,0,0,0,0,5] -> [1,2,3,4,5,0]
[0,1,2,3] -> [3,2,1,0]
[0,1,1,1] -> [3,0,1,2]
[0,1,1,2,1,0] -> [4,0,2,1,3,5]

Victorioso

Este es el , por lo que gana la respuesta más corta.

varilla
fuente
1
¿El programa también puede tomar la longitud de la lista como entrada?
mbomb007
@ mbomb007 no.
Rod
¿Podemos usar pasos (n-1) en su lugar? El primero es innecesario, ya que siempre es cero.
GB
@GB seguro, siempre que la salida sea correcta, puede usar cualquier algoritmo
Rod

Respuestas:

14

Jalea , 12 bytes

L!_UÆ¡$œ?J’U

Pruébalo en línea!

Explicación

Básicamente, podemos ver las dos listas (la entrada y la salida) como codificación de un número entero; la entrada codifica un número entero en base factorial, y la salida codifica un número entero como permutación. Afortunadamente, Jelly tiene incorporados que ya están muy cerca de ambas codificaciones, por lo que es simplemente una cuestión de escribir pequeños trozos de código para convertirlos en un entero y luego volver a la otra codificación.

L!_UÆ¡$œ?J’U
   U           Reverse {the input}
    Æ¡         and convert from base factorial to integer;
  _   $        subtract that from
L!             the factorial of the length of {the input};
       œ?      then take the nth permutation of
         J     [1,2,...,l], where l is the length of {the input},
          ’    subtract 1 from every elevent,
           U   and reverse it

En el caso del factorial base, podemos observar que el primer elemento de la lista debe ser 0, el segundo puede ser 0 o 1, el tercero debe ser 0/1/2, y así sucesivamente. Por lo tanto, tenemos que invertir la entrada para obtener sus elementos en el orden de escritura normal para la conversión de base.

Además, para que los órdenes relativos de la conversión factorial y la conversión de permutación coincidan con la operación que utiliza la ordenación por inserción, debemos hacer dos ajustes: invertir la secuencia de las permutaciones e invertir el orden de la lista de salida. Revertir la lista de resultados es bastante fácil, ya que solo necesita un Ual final del programa. Para invertir la secuencia de permutaciones, restamos del factorial de la longitud de entrada (esto funciona porque el factorial base produce un número en el rango de 0 a (longitud! -1), mientras que las permutaciones están numeradas por Jelly de 1 a longitud! , produciendo un off-by-one implícito que cancela el off-by-one que normalmente se obtiene al restar un índice de permutación de un factorial).

Jelly , 9 bytes, en colaboración con @JonathanAllan

UÆ¡Nœ?J’U

Esta versión del programa es muy similar, pero utiliza un método diferente para revertir la secuencia de permutaciones; simplemente negar la entrada con Nes suficiente para hacer que œ?el orden se trate en reversa. Aparte de eso, funciona de manera idéntica al programa anterior.

Pruébalo en línea!


fuente
44
O_O ¿Qué hechicería es esta?
DLosc
Oh, bueno, sabía que mis átomos Æ¡y yo œ?funcionarían para esto (ya había comenzado a tratar de usarlos para este desafío antes, estaba tan cerca, solo necesitaba el L!allí).
Jonathan Allan
Excelente código!
Greg Martin
1
De hecho, puede hacerlo en 9 bytes con UÆ¡Nœ?L’Uporque implementé œ?(y similares) para actuar de forma modular (como si estuvieran usando listas Jelly). El Njusto se indexa con el valor negativo. Nota: Cambié Ja L: esto es solo porque, dado un número, de todos modos hace un rango bajo el capó).
Jonathan Allan
6

Mathematica, 92 bytes

Permute[Range[l=Length@#]-1,(c=Cycles@{#}&)@{}©##&@@c[i-0~Range~#[[i]]]~Table~{i,l,1,-1}]&

Función pura que toma una lista de enteros no negativos como entrada y devuelve una lista de enteros no negativos. El código anterior contiene un ©, que es incorrecto: es un marcador de posición para el símbolo de 3 bytes U + F3DE, que Mathematica representa por un círculo con un punto en él, y que representa la composición de las permutaciones.

c=Cycles@{#}&define una función que convierte una lista de enteros en un Cyclesobjeto que representa una permutación; por ejemplo, c[{3,4}]son los elementos de intercambio de transposición 3 y 4 de una lista. c[i-0~Range~#[[i]]]~Table~{i,l,1,-1}]toma la lista de entrada y genera las permutaciones necesarias para deshacer el orden de inserción. Luego c@{}©##&@@compone todas estas permutaciones juntas, comenzando con la permutación de identidad c@{}. Finalmente, Permute[Range[l=Length@#]-1,...]aplica esta permutación a la lista indexada 0 de longitud apropiada.

Greg Martin
fuente
1
¿Qué no incorporado? Seguramente ...
Jonathan Allan
3
@{#}&)@{}©##&@@da miedo.
Yytsi
6

Python 2, 79 68 bytes

Gracias a Krazor por guardar 10 bytes.

Gracias a TuukkaX por guardar 1 byte

a=input();b=range(len(a));print[b.pop(j-a[j])for j in b[::-1]][::-1]

Funciona generando los movimientos en reversa

adicto a las matemáticas
fuente
2
¡Haz eso 66 ! ¿Qué tal: a=input();b=range(len(a));print[b.pop(j-a[j]) for j in b[::-1]][::-1]. Lista de comprensiones ftw!
FMaz
1
@Krazor Tienes un espacio que podría eliminarse antes for, así que supongo que 65 supongo: D
Yytsi
@Krazor Resulta que la comprensión de la lista no funcionó, ¡pero me gustó la idea de usar b [:: - 1]!
adicto a las matemáticas
¿De ninguna manera? Comenté con el móvil, tal vez escribí algo mal. ¿Qué parte no funciona? Para mí, interpretó correctamente y cumplió todos los casos de prueba.
FMaz
@ Krazor Oh, vaya, no, tienes razón. Yo fui quien lo escribió mal durante las pruebas.
adicto a las matemáticas
5

JavaScript (ES6), 69 65 63 bytes

a=>a.reverse(b=[...a.keys()]).map(o=>+b.splice(~o,1)).reverse()

Molestamente, tanto la entrada como la salida están en el orden incorrecto. Editar: Guardado 4 bytes gracias a @Arnauld. Guardado 2 bytes gracias a @ETHproductions.

Neil
fuente
Todavía estaba tratando de encontrar una mejor manera, pero fuiste mucho más rápido. ¡Buena esa!
Arnauld
1
No necesitas i, ¿verdad?
Arnauld
@Arnauld Aparentemente no. Comencé tratando de entender la respuesta de Python, y acabo de darme cuenta de que en realidad no usa i...
Neil
1
Fácil -2:o=>+b.splice(~o,1)
ETHproductions
3

JavaScript (ES6), 73 71 bytes

Ahorró 2 bytes gracias a ETHproductions

m=>(a=m.map((_,i)=>j=i)).map(_=>a.splice(j,0,+a.splice(j-m[j--],1)))&&a

Casos de prueba

Arnauld
fuente
Buena manera de obtener la longitud y el rango al mismo tiempo. Iba a sugerir a=m.map(_=>j++,j=0), pero esa es la misma longitud y estoy seguro de que ya lo has probado.
ETHproductions
@ETHproductions Tienes razón: también lo he probado. :-) (Vale la pena señalar que esto no es equivalente: esto se establecería jen a.lengthlugar de a.length-1y requeriría a.splice(--j,0,a.splice(j-m[j],1)[0]))
Arnauld
Heh, también pensé en eso, pero no pensé que valiera la pena mencionarlo porque tiene la misma duración
ETHproductions
1
Fácil -2:+a.splice(j-m[j--],1)
ETHproductions
2

Haskell , 85 bytes

f x|n<-length x-1=reverse x#[n,n-1..0]
(n:r)#l=r#(take n l++drop(n+1)l)++[l!!n]
x#l=x

Pruébalo en línea! Ejemplo de uso: f [0,1,1,2,1,0]rendimientos [4,0,2,1,3,5].

f xllama a la función #con la lista xinvertida y una lista [length x - 1, length x - 2, ... , 0]. (n:r)#lrealiza la ordenación de inserción inversa sacando recursivamente el nelemento th l, donde l!!nproduce el nelemento th y take n l++drop(n+1)lla lista lcon el nelemento th eliminado.

Laikoni
fuente
Haskell, muy hermosa.
FMaz
1

perl, 61 bytes

@o=@p=0..@ARGV-1;splice@o,$_,0,splice@o,$_-pop,1for reverse@p

La salida termina en matriz @o. Ejemplo con matriz de entrada como argumentos de línea de comando:

perl -le'@o=@p=0..@ARGV-1;splice@o,$_,0,splice@o,$_-pop,1for reverse@p;print@o' 0 1 1 2 1 0
402135
Kjetil S.
fuente
1

Ruby, 49 bytes

->l{(w=l.size).times{l.insert(l.shift+w-=1,w)};l}

Realiza la "inserción inversa" en su lugar dentro de la lista, comenzando con el número más grande.

GB
fuente