Expressing an arbitrary permutation as a sequence of (insert, move, delete) operations

Question

Suppose I have two strings. Call them $A$ and $B$. Neither string has any repeated characters.

How can I find the shortest sequence of insert, move, and delete operation that turns $A$ into $B$, where:

• insert(char, offset) inserts char at the given offset in the string
• move(from_offset, to_offset) moves the character currently at offset from_offset to a new position so that it has offset to_offset
• delete(offset) deletes the character at offset

Example application: You do a database query and show the results on your website. Later, you rerun the database query and discover that the results have changed. You want to change what is on the page to match what is currently in the database using the minimum number of DOM operations. There are two reasons why you'd want the shortest sequence of operations. First, efficiency. When only a few records change, you want to make sure that you do $\mathcal{O}(1)$ rather than $\mathcal{O}(n)$ DOM operations, since they are expensive. Second, correctness. If an item moved from one position to another, you want to move the associated DOM nodes in a single operation, without destroying and recreating them. Otherwise you will lose focus state, the content of <input> elements, and so forth.

Answer 1

I suggest taking a look at the edit distance algorithm. Instead of just calculating the distance, you'll want to record your minimum weight path through the array and return that.