# Removing and reinserting elements to minimally mimic a changeset

Let's say that there is a tower of blocks labelled from top to bottom $1$ to $n$. Somebody comes along and removes a block and reinserts it somewhere in the tower (making space as needed). As they move these blocks one at a time, they write down in order which index they moved a block to (index starting at 1). For example, they take the block 5 from the 5th index and squeeze it into between the 6th and 7th making it the 7th index. They write down "block 5 to index 7". They can make as many moves as they like and move each block as many times as they like.

Note that the index "moved to" is the index of the block after the removal and insertion are complete.

Someone else finds the changeset the original person created. Knowing the size of the tower and having the list of changes, they must write another changeset that would have the same results as the first but with at most one move per block and the moves must take place in the order that the blocks were originally moved in without latter duplicates. This also means that only blocks of the original changeset can be moved.

I came up with one which is to repeat the steps in order excluding those where the block is moved again later. This seemed to work in some cases but not all.

Is there an algorithm to solve this problem?

• Say the n is 4 [1, 2, 3, 4], someone moves them and now there is [4, 1, 3, 2] and the task is to write 4->1, 4->3?
– Evil
Commented May 22, 2018 at 4:47
• @Evil For the most part, I was using block #'s to describe what moved and indices to describe where to. So it would be [block] 4-> [index] 1, [block] 3-> [index] 3.
– Knox
Commented May 22, 2018 at 14:41
• Hints given by D.W. seems sufficient, do you understand them?
– Evil
Commented May 22, 2018 at 22:21
• I forgot an important requirement and I'm not sure if it would have been better to make a new questions: "the moves must take place in the order that the blocks were originally moved in without latter duplicates."
– Knox
Commented May 22, 2018 at 22:29
• It does not matter at all, it only determines order of moves you have to provide as the result, so it will be just 1 instead of any possible. So it does not require new question.
– Evil
Commented May 22, 2018 at 23:29