如何查找两个列表之间的更改，其中包含不可移动的项目（PHP）

Question

我正在尝试获取两个文章列表之间的更改，以便为两个列表之间的过渡设置动画。可以添加、删除或移动（不可交换）文章。

但是，有些文章无法移动，并且在每次转换中，所有其他文章都应移至这些文章下方。

例如，如果每个数字代表一个文章id，粗体代表不可移动的文章，那么： [1, 2, 3, 4, 5, 6] 可能会变成：[2, 4, 1 , 6, 7]

我需要计算出所需的更改，例如在这种情况下：

• 在 4 之后移动 1
• 删除 5
• 在 6 之后添加 7

我一直在使用 diff 算法，但是它不理解不可移动的项目，所以它可能建议：

• 将 2 移至开头
• 在 2 之后移动 4
• 删除 5
• 在 6 之后添加 7

我尝试了各种方法，但无法让它可靠地工作。

Answer 1

将不可移动的项目向左移动 3 个位置与将其旁边的 3 个可移动的项目向右移动 1 个位置是一样的。使用当前的 diff 算法，但是当它想要将不可移动的项目移至其旁边的项目时。

---

UPD。每篇文章无需多次移动。

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

这是一个有趣的问题！

Answer 2

这是最终的代码，感谢 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;
}

此时我们可以执行 $removals，然后执行 $moves 然后 $additions