作爲一系列動作的數組差異

Question

簡而言之：我有兩個可能不同的數組，我想將差異/變換看作一系列「動作」（添加和刪除）。即，在一個基本的例子：

Current: [a, b, d] 
Desired: [a, b, c, d] 
Actions: Add c in position 2 

基本上，所述指令如何，使得它有相同的構件，並順序作爲所需陣列的當前陣列變換。對於我的應用程序，每次更改都會觸發更新UI等事件，所以如果這些操作不是「多餘的」，那將是非常可取的：也就是說，上述操作可能是remove d, add c @ 2, add d @ 3，但這會在別處導致大量不需要的處理在系統中。

也許是另一個例子可能有助於說明：

Current: [a, b, d] 
Desired: [b, c, d, a] 
Actions: remove a, add c @ 1, add a @ 3 

我想這是一件已經被解決過，但它有點困難，因爲「陣列差」來搜索它不給你正確的結果。

如果很重要，我正在Javascript中實現這一點，但我猜算法是語言不可知的。

Answer 1

這確實存在，它被稱爲edit distance。基本算法不記得那種編輯，但它很容易修改。

一種類型的編輯距離是Levenshtein distance。這個維基百科頁面包含一些您可能會覺得有用的代碼片段。

Hirschberg's algorithm也可能有用。