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.


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).


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

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]


This is , so the shortest answer wins.

  • 1
    \$\begingroup\$ May the program also take the length of the list as input? \$\endgroup\$
    – mbomb007
    Commented Feb 17, 2017 at 19:18
  • \$\begingroup\$ @mbomb007 nope. \$\endgroup\$
    – Rod
    Commented Feb 17, 2017 at 20:40
  • \$\begingroup\$ Can we use (n-1) steps instead? The first one is unnecessary, since it's always zero. \$\endgroup\$
    – G B
    Commented Feb 21, 2017 at 10:50
  • \$\begingroup\$ @GB sure, as long the output is right, you can use any algorithm \$\endgroup\$
    – Rod
    Commented Feb 21, 2017 at 11:03

8 Answers 8


Jelly, 12 bytes


Try it online!


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.

   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


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!

  • 4
    \$\begingroup\$ O_O What sorcery is this? \$\endgroup\$
    – DLosc
    Commented Feb 17, 2017 at 19:43
  • \$\begingroup\$ Oh nice - I knew my Æ¡ and œ? atoms would work for this (I had already started trying to use them for this challenge earlier - I was so close, just needed the L! in there). \$\endgroup\$ Commented Feb 17, 2017 at 19:55
  • \$\begingroup\$ Excellent code! \$\endgroup\$ Commented Feb 17, 2017 at 22:23
  • 1
    \$\begingroup\$ In fact, you can do it in 9 bytes with UÆ¡Nœ?L’U because I implemented œ? (and similar) to act modularly (as if they were using Jelly lists). The N just indexes in with the negative value. Note: I changed J to L - this is just because given a number it makes a range under-the-hood anyway). \$\endgroup\$ Commented Feb 19, 2017 at 0:35

Mathematica, 92 bytes


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.

  • 1
    \$\begingroup\$ What no built-in?! Surely... \$\endgroup\$ Commented Feb 17, 2017 at 21:19
  • 3
    \$\begingroup\$ @{#}&)@{}©##&@@ looks scary. \$\endgroup\$
    – Yytsi
    Commented Feb 18, 2017 at 6:49

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

  • 2
    \$\begingroup\$ Make that 66! How about: a=input();b=range(len(a));print[b.pop(j-a[j]) for j in b[::-1]][::-1]. List comprehensions ftw! \$\endgroup\$
    – FMaz
    Commented Feb 18, 2017 at 13:23
  • 1
    \$\begingroup\$ @Krazor You have a space that could be removed before for, so make that 65 I guess :D \$\endgroup\$
    – Yytsi
    Commented Feb 18, 2017 at 15:28
  • \$\begingroup\$ @Krazor Turns out the list comprehension didn't quite work, but I liked the idea of using b[::-1] ! \$\endgroup\$ Commented Feb 18, 2017 at 18:01
  • \$\begingroup\$ No way? I commented with mobile, maybe I mistyped something. Which part does not work? For me, it interpreted correctly and fulfilled all test cases. \$\endgroup\$
    – FMaz
    Commented Feb 18, 2017 at 18:27
  • \$\begingroup\$ @Krazor Oh whoops, no you're right. I'm the one who mistyped it while testing. \$\endgroup\$ Commented Feb 18, 2017 at 18:35

JavaScript (ES6), 69 65 63 bytes


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

  • \$\begingroup\$ I was still trying to find a better way but you were much faster. Nice one! \$\endgroup\$
    – Arnauld
    Commented Feb 17, 2017 at 23:46
  • 1
    \$\begingroup\$ You don't need i, do you? \$\endgroup\$
    – Arnauld
    Commented Feb 17, 2017 at 23:52
  • \$\begingroup\$ @Arnauld Apparently not. I started by trying to understand the Python answer, and I've only just noticed that it doesn't actually use i... \$\endgroup\$
    – Neil
    Commented Feb 18, 2017 at 0:33
  • 1
    \$\begingroup\$ Easy -2: o=>+b.splice(~o,1) \$\endgroup\$ Commented Feb 18, 2017 at 2:53

JavaScript (ES6), 73 71 bytes

Saved 2 bytes thanks to ETHproductions


Test cases

let f =


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]

  • \$\begingroup\$ Nice way of getting the length and the range at the same time. I was gonna suggest a=m.map(_=>j++,j=0), but that's the same length and I'm sure you've already tried it. \$\endgroup\$ Commented Feb 17, 2017 at 22:50
  • \$\begingroup\$ @ETHproductions You're right: I've tried it as well. :-) (It may be worth noting that this is not equivalent: this would set j to a.length rather than a.length-1 and would require a.splice(--j,0,a.splice(j-m[j],1)[0])) \$\endgroup\$
    – Arnauld
    Commented Feb 17, 2017 at 23:07
  • \$\begingroup\$ Heh, I thought of that too, but I didn't think it was worth mentioning because it's the same length \$\endgroup\$ Commented Feb 18, 2017 at 0:03
  • 1
    \$\begingroup\$ Easy -2: +a.splice(j-m[j--],1) \$\endgroup\$ Commented Feb 18, 2017 at 2:54

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]

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.

  • \$\begingroup\$ Haskell, so beautiful. \$\endgroup\$
    – FMaz
    Commented Feb 18, 2017 at 21:16

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

Ruby, 49 bytes


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.