Reverse Insertion sort

Question

Objective

Generate the original scrambled list, from the movements that an Insertion Sort would do to sort it. The original list will have all numbers from 0 to N-1(inclusive) where N is the size of the input.

Input

A list containing the necessary moves to sort the list. Each value represents the amount of slots displaced by the original (scrambled) number to be in his right position , keep in mind that this process is from the left to the right.
The value at (0-indexed) position i in the input list will be between 0 and i inclusive.
You don't need to handle invalid inputs, any behaviour is acceptable in this case (crash, infinite loop, etc).

Output

The scrambled list

Step-by-step to generate the moves

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]

So, for the input [0,1,1,2,1,0] your program need to output [4,0,2,1,3,5].
Keep in mind that the movements aren't to the position in the (final) sorted list, but in the sorted segment(the bolded section)

Test Cases

[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]

Winning

This is code-golf, so the shortest answer wins.

Answer 1

Jelly, 12 bytes

L!_UÆ¡$œ?J’U

Try it online!

Explanation

We can basically see the two lists (the input and the output) as encoding an integer; the input encodes an integer in factorial base, and the output encodes an integer as a permutation. Luckily, Jelly has builtins that are already very close to both of these encodings, so it's simply a matter of writing small pieces of code to convert to an integer, then back to the other encoding.

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

In the case of base factorial, we can observe that the first element of the list must be 0, the second can be 0 or 1, the third must be 0/1/2, and so on. Thus, we have to reverse the input in order to get its elements into the normal writing order for base conversion.

Additionally, for the relative orders of the factorial conversion and the permutation conversion to match up with the operation that insertion sort uses, we need to make two adjustments: reversing the sequence of the permutations, and reversing the order of the output list. Reversing the output list is easy enough, needing only a U at the end of the program. To reverse the sequence of permutations, we subtract from the factorial of the input length (this works because the base factorial produces a number in the range 0 to (length!-1), whereas the permutations are numbered by Jelly from 1 to length!, producing an implicit off-by-one that cancels out the off-by-one that you normally get when subtracting a permutation index from a factorial).

Jelly, 9 bytes, in collaboration with @JonathanAllan

UÆ¡Nœ?J’U

This version of the program is very similar, but uses a different method of reversing the sequence of permutations; simply negating the input with N is enough to make œ? treat the order in reverse. Apart from that, it works identically to the previous program.

Try it online!

Answer 2

Mathematica, 92 bytes

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

Pure function taking a list of nonnegative integers as input and returning a list of nonnegative integers. The above code contains a ©, which is incorrect: it's a placeholder for the 3-byte symbol U+F3DE, which Mathematica represents by a circle with a dot in it, and which represents composition of permutations.

c=Cycles@{#}& defines a function that converts a list of integers into a Cycles object representing a permutation; for example, c[{3,4}] is the transposition swapping elements 3 and 4 of a list. c[i-0~Range~#[[i]]]~Table~{i,l,1,-1}] takes the input list and generates the permutations necessary to undo the insertion sort. Then c@{}©##&@@ composes all of these permutations together, starting with the identity permutation c@{}. Finally, Permute[Range[l=Length@#]-1,...] applies this permutation to the 0-indexed list of appropriate length.

Answer 3

Python 2, 79 68 bytes

Thanks to Krazor for saving 10 bytes

Thanks to TuukkaX for saving 1 byte

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

Works by generating the moves in reverse

Answer 4

JavaScript (ES6), 69 65 63 bytes

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

Annoyingly both input and output are in the wrong order. Edit: Saved 4 bytes thanks to @Arnauld. Saved 2 bytes thanks to @ETHproductions.

Answer 5

JavaScript (ES6), 73 71 bytes

Saved 2 bytes thanks to ETHproductions

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

Test cases

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]

Answer 6

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

Try it online! Example usage: f [0,1,1,2,1,0] yields [4,0,2,1,3,5].

f x calls the function # with list x reversed and a list [length x - 1, length x - 2, ... , 0]. (n:r)#l performs the reverse insertion sort by recursively taking the nth element out of l, where l!!n yields the nth element and take n l++drop(n+1)l yields the list l with the nth element removed.

Answer 7

perl, 61 bytes

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

Output ends up in array @o. Example with input array as command line arguments:

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

Answer 8

Ruby, 49 bytes

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

Performs the "reverse insertion" in place inside the list, starting with the largest number.