How to find the changes between two lists, with immovable items (PHP)

Question

I'm trying to get the changes between two lists of articles in order to animate the transition between the two lists. Articles can be added, removed or moved (not swapped).

However some articles can't be moved, and in each transition all other articles should be moved below those articles.

For example, if each number represents an article id, and bold represents immovable articles, then: [1, 2, 3, 4, 5, 6] might become: [2, 4, 1, 6, 7]

I need to work out the changes required, for example in this case:

• Move 1 after 4
• Remove 5
• Add 7 after 6

I have been using a diff algorithm, however it doesn't understand immovable items, so it might suggest:

• Move 2 to the beginning
• Move 4 after 2
• Remove 5
• Add 7 after 6

I've tried various things, but can't get it to work reliably.

Answer 1

Moving an immovable item 3 places left is the same thing as moving 3 movable items next to it 1 place right. Use your current diff algorithm, but when it wants to move an immovable item switch to those next to it instead.

---

UPD. Without multiple moves per article.

Transformations:

1. Remove numbers that are not in the second list (for each item n if not in_list(final_list) then say(n removed)).
   [1 2* 4* 5 6] // say("remove 3")
   [1 2* 4* 6]   // say("remove 5")       
2. Make an empty list size of the final list.
   [_ _ _ _ _]
3. Prefill it with immovable numbers in their final positions.
   [2* 4* _ _ _]
4. Loop through movable items from the first list moving them to their final positions
   [2* 4* 1 _ _] // say("move 1 after 4")
   [2* 4* 1 6 _] // say("move 6 after 1")
5. Add new items
   [2* 4* 1 6 7] // say("add 7 after 6")

It was a fun problem to solve!

Answer 2

Here's the final code, thanks to Alexey:

$immovable = array(2);
$current = array(1,2,8,3,4,5,6);
$new = array(2,7,6,5,4,3,1);

$additions = $additionsCopy = array_diff($new, $current);
foreach($additions as $key => $addition) {
  $after = array_key($new, $addition)-1;
  $additions[$key] = array(
    'value' => $addition, 
    'after' => ($after < 0 ? 0 : $new[$after])
  );
}
for($key = 0; $key < count($new); $key++) {
  if(in_array($new[$key], $additionsCopy)) 
    $new = array_remove($new, $key--);
}

$removals = array_diff($current, $new);
for($key = 0; $key < count($current); $key++) {
  if(in_array($current[$key], $removals)) 
    $current = array_remove($current, $key--);
}

$lastImmovable = -1;
foreach($new as $key => $item) if(in_array($item, $immovable)) 
  $lastImmovable = $key;

$prev = $lastImmovable < 0 ? 0 : $new[$lastImmovable];
foreach($new as $key => $item) if (!in_array($item, $immovable)) {
  $moves[] = array('value' => $item, 'after' =>$prev);
  $prev = $item;
}

At this point we can perform $removals, then $moves then $additions