Your problem is that the source positions are expressed in the prior
order while the destination positions are in the final order. When you do
1->7, you don't know yet where 7 is in the prior order. You need to make
adjustments for all the moves.
The original moves are:
from: [ 1, 2, 6, 7]
to: [ 7, 4, 2, 8]
Let's first tranform the positions as if we were removing all elements
first, then inserting the elements at the new positions. For the
from positions, proceed from the left: removing at 1 shifts
positions (2,6,7) down to (1,5,6). Removing at 1 again shifts (5,6) down
to (4,5). Removing at 5 shifts the 5 down to 4. For every position in
from all subsequent positions with a larger or equal index
must be decremented. We get:
from: [ 1, 1, 4, 4]
to positions, proceed from the end: Position 8 is
correct. Position 2 is also correct, but it means the prior (7,4) were
actually (6,3) at the time of insertion. So we adjust them. Similarily,
inserting at 3 means the prior position 6 was at 5.
So, for the
to array, we proceed from the end, for every
position we decrement all prior positions that have a larger index. The
to array becomes:
to: [ 5, 3, 2, 8]
What we have is the correct positions for 4 removals followed by 4
insertions. Now we want to interleave the removals and the insertions.
Insertion at 5 must be done before the removals at (1, 1, 4). 5 is
larger than any of these, so it won't affect the positions (1, 1, 4), but
the 5 is affected because the 3 removals are done left of the insertion
point. 5 becomes 8.
Insertion at 3 must come before removals at (4, 4). Since 3 is smaller
than the 4's, the position 3 is unaffected by the removals but the removals
must be incremented, to positions (5, 5).
Insertion at 2 comes before the last removal at 5 (was 4). It is
smaller, therefore the 5 is adjusted to 6.
for i = 0 to size-1
for j = size-1 to i+1
if from[j] < to[i] then increment to[i]
else decrement from[j]
We should get the arrays:
from: [ 1, 1, 5, 6]
to: [ 8, 3, 2, 8]
These are the final moves to execute with the correct positions at the
time of the move. The moves can be read from left to right: Remove at 1,
insert at 8. Remove at 1, insert at 3. Remove at 5, insert at 2. Remove
at 6, insert at 8.