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.