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 código de golf , por lo que gana la respuesta más corta.

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!

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.

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

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.

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

let f =

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

console.log(JSON.stringify(f([0,0,0])));       // -> [0,1,2]
console.log(JSON.stringify(f([0,1,0,1])));     // -> [1,0,3,2]
console.log(JSON.stringify(f([0,0,0,0,0,5]))); // -> [1,2,3,4,5,0]
console.log(JSON.stringify(f([0,1,2,3])));     // -> [3,2,1,0]
console.log(JSON.stringify(f([0,1,1,1])));     // -> [3,0,1,2]
console.log(JSON.stringify(f([0,1,1,2,1,0]))); // -> [4,0,2,1,3,5]

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.

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

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.