Transposition of any characters in Damerau–Levenshtein edit distance computation Is it possible to modify the computation of Damerau–Levenshtein distance to take into account not only the transposition of adjacent characters, but the transposition of any characters?

Maybe some heuristic would help?

update

I will identify the application.

I have two sequences of characters. An "Old" one and a "New" one. I need to compute editorial prescription (is it a correct English term?) as a series of actions that could be applied to an "Old" sequence to make it equal to a "New" one.

There are not more than 10-20 characters in a sequence in most cases, thus O(n) is not so important.

The important part is... characters in that "Old" sequence have some metadata assigned to each other. That's why transposition is more welcome than remove/insert when it's possible.

My goal is to make an "Old" sequence equal to a "New" one preserving that metadata as much as possible.
Thanks for updating the question - here goes an answer tailored to your application:

Since we are dealing with realatively small instances we could define an optimal algorithm based on a backtracking branch and bound schema (Presentation on B&amp;B - easy, Something more thorough with common application) by constructing a "path" of permutations with following assuptions:


We want to promote swaps to preserve metadata - cost = 1
We want to penilize other operations but allow them if nessesary - cost = 2
Dissalow "stupid" moves ex. Inserting a letter that's not in the target sequence
Innitial Upper Bound = Levensthein (plain version not the Damerau extension) x 2 (because of the costs)
Lower Bound current path cost + how many letters (disregard positions) do not match in current and target sequences Example:
i have ABCCDD
i want CCWGZDD


the cost added to current path is (1 (W) + 1 (G) + 1 (Z) + 2 (D)) = 5
(probably there is room for a better Lower Bound but it's usually non-trivial to come up with one)


Each time you get to target sequence and path cost is lower than Upper Bound - update it and backtrack.
Each time your Lower Bound exeeds Upper Bound - backtrack 


Please google backtracking algorithms and branch and bound for more information. Should you like the solution but have no idea how to go about implementing it please let me know (PW) I'll try to cook-up some pseudocode for you.   

The algorithm in worst case is exponential but on real istances should perform very well.