Array difference as a series of actions

Question

In short: I have two arrays which may be different, and I'll like to get the difference/transformation as a series of "actions" (adds and removes). That is, in a basic example:

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

Basically, the instructions are how to transform the current array so that it's got the same members and order as the desired array. For my application, each change triggers events which update UI and so on, so it would be highly preferable if the actions were not "redundant": that is, the above could have been remove d, add c @ 2, add d @ 3, but this would cause a lot of unwanted processing elsewhere in the system.

Perhaps as another example which might help illustrate:

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

I figure this is something which has been solved before, but it's kinda difficult to search for it since "array difference" doesn't give you the right results.

If it matters, I'm implementing this in Javascript, but I guess the algorithm is language agnostic.

Answer 1

This does indeed exists, it's called the edit distance. The basic algorithm doesn't remember the kind of edits, but it's easily modified.

One type of edit distance is the Levenshtein distance. This wikipedia page contains some code snippets you may find useful.

Hirschberg's algorithm may also be useful.