<p>Thanks for updating the question - here goes an answer tailored to your application:</p>

<p>Since we are dealing with realatively small instances we could define an optimal algorithm based on a backtracking branch and bound schema (<a href="http://www.google.pl/url?sa=t&amp;rct=j&amp;q=&amp;esrc=s&amp;source=web&amp;cd=2&amp;ved=0CF8QFjAB&amp;url=http://www.academic.marist.edu/~jzbv/algorithms/StudentProjects/BacktrackingandBandB.ppt&amp;ei=ObXkT9rqI83ntQaStbz5CA&amp;usg=AFQjCNHJFlUnnQjUemvLCbg5FL0QWzFdPw&amp;sig2=R783eQNjhJQ-hMS-SeHyDg" rel="nofollow">Presentation on B&amp;B - easy</a>, <a href="http://www.win.tue.nl/~mdberg/Onderwijs/Algoritmiek_Material/backtracking.pdf" rel="nofollow">Something more thorough with common application</a>) by constructing a "path" of permutations with following assuptions:</p>

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

<p>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)</p>

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

<p>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.   </p>

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

CC BY-SA 3.0
2012-06-27T11:34:04.353Z
Not exactly what I need, but it is something to think about. Thank you!
Roman Yankovsky
CC BY-SA 3.0
2012-06-22T18:27:54.473Z
2012-06-23T11:18:43.403Z
2012-06-23T11:18:43.403Z
JohnnyM
<p>I agree to user834 comment - this seems like exacly this kind of problem. It is not simplified because after each swap we can perform another and another ... so in each step of the algorithm we have O(n^2) possible swaps. </p>

<p>It would be helpful if you could identify the application of this question - perhaps the question itself is ill-posed. </p>

<p>I would also appreciate if you could elaborate on the cost-metric you would like to use for swaps other than adjectant - would it still be = 1?</p>

<p>If you a sure that this is exactly what you want I could propose a following metaheuristic based on local search (<a href="http://www.google.pl/url?sa=t&amp;rct=j&amp;q=&amp;esrc=s&amp;source=web&amp;cd=2&amp;ved=0CFQQFjAB&amp;url=http://cs.gmu.edu/~sean/book/metaheuristics/Essentials.pdf&amp;ei=mLbjT4zTFo-e-Qbaz7iTCg&amp;usg=AFQjCNGA7zwoYBsB2X7GHl9FDl7RkbK4Yg&amp;sig2=tdfEzqbCsUCBOoSugX2jvg" rel="nofollow">An accessible publication about local search and other metaheurestics</a>):</p>

<p>Define following: </p>

<p>neighbourhood (possible move) | size:</p>

<ul>
<li>swap | O(n^2)</li>
<li>letter change | O(n*alphabethSize)</li>
<li>delete        | O(n)</li>
<li>insert        | O(n*alphabethSize)</li>
</ul>

<p>Steps:</p>

<ol>
<li>Try each move and evaluate the D-L distance of the new sequence to target sequence.</li>
<li>Chose best move.</li>
<li>Go back to 1.</li>
</ol>

<p>Stop if you have the target sequence or there are no more moves that get you closer to it (local minimum).</p>

<p>Possible execution optimisations:</p>

<ul>
<li>don't consider letters that are not in target seqence</li>
<li>candidate moves (see the .pdf)</li>
<li>you could use the greedy version of local search - choose the first move that betters the distance to target sequence (much faster but more likely to produce worse results). Also remember to evaluate the moves in random order in this version.</li>
</ul>

<p>Optimality guarantee: <strong>none</strong> this is a heurestic. </p>

<p><strong>Guys please justify downvoting if you can.</strong></p>

CC BY-SA 3.0
2012-06-22T11:12:48.400Z
Thank you for this answer. It's not my downvote. I have updated my question, hope this will help.
Roman Yankovsky
CC BY-SA 3.0
2012-06-22T00:18:53.427Z
2012-06-22T10:42:20.113Z
2012-06-22T10:42:20.113Z
JohnnyM
<p>Is it possible to modify the computation of <a href="http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance" rel="nofollow">Damerau–Levenshtein distance</a> to take into account not only the transposition of <strong>adjacent</strong> characters, but the transposition of <strong>any</strong> characters?</p>

<p>Maybe some heuristic would help?</p>

<p><strong>update</strong></p>

<p>I will identify the application.</p>

<p>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.</p>

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

<p>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.</p>

<p>My goal is to make an "Old" sequence equal to a "New" one preserving that metadata as much as possible.</p>

CC BY-SA 3.0
2012-06-19T22:14:19.677Z
@Kaveh, my point with "string-matching" tag was that a few questions about Levenshtein distance have this tag. But it's up to you.
Roman Yankovsky
CC BY-SA 3.0
2012-06-21T21:33:36.637Z
IMHO that doesn't make the [tag:string-matching] tag appropriate for this question but you can add it back if you want.
Kaveh
CC BY-SA 3.0
2012-06-21T22:06:30.200Z
This is suspiciously like finding the minimum number of permutations to get from one element to another which, if I'm not mistaken, is NP-Hard.  Maybe allowing all $\binom{n}{2}$ swaps simplifies it, I'm not sure.
user834
CC BY-SA 3.0
2012-06-22T08:39:54.933Z
I think this variant does not fulfill Bellman's optimality criterion anymore, so dynamic programming won't work. It smells similar to [secondary structure prediction](https://en.wikipedia.org/wiki/Secondary_structure_prediction) with [pseudoknots](https://en.wikipedia.org/wiki/Pseudoknot), which is known to be NP-hard (as opposed to cubic time by DP without pseudoknots).
Raphael
CC BY-SA 3.0
2012-06-22T10:05:38.517Z
If you ignore everything but the swapping, I think this is related to [decomposing permutations](https://groups.google.com/forum/?fromgroups#!topic/sci.math/gSIYN9-zKzA). Because what you want to do is implement a permutation via swaps. First, decompose the permutation into cycles (fast and easy), and then get the necessary swaps from each cycle. Won't help with the other edit operations, though – and mixing the two ain't trivial, I think.
Magnus Lie Hetland
<co.combinatorics><it.information-theory><coding-theory>
Transposition of any characters in Damerau–Levenshtein edit distance computation
Roman Yankovsky
# Transposition of any characters in Damerau–Levenshtein edit distance computation

(Asked by: username_0 on 2012-06-19)

Is it possible to modify the computation of [Damerau–Levenshtein distance](http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_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.

**Tags:** co.combinatorics, it.information-theory, coding-theory

> **Comments:**
> **username_0**: @username_1, my point with "string-matching" tag was that a few questions about Levenshtein distance have this tag. But it's up to you.  
> **username_1**: IMHO that doesn't make the [tag:string-matching] tag appropriate for this question but you can add it back if you want.  
> **username_2**: This is suspiciously like finding the minimum number of permutations to get from one element to another which, if I'm not mistaken, is NP-Hard.  Maybe allowing all $\binom{n}{2}$ swaps simplifies it, I'm not sure.  
> **username_3**: I think this variant does not fulfill Bellman's optimality criterion anymore, so dynamic programming won't work. It smells similar to [secondary structure prediction](https://en.wikipedia.org/wiki/Secondary_structure_prediction) with [pseudoknots](https://en.wikipedia.org/wiki/Pseudoknot), which is known to be NP-hard (as opposed to cubic time by DP without pseudoknots).  
> **username_4**: If you ignore everything but the swapping, I think this is related to [decomposing permutations](https://groups.google.com/forum/?fromgroups#!topic/sci.math/gSIYN9-zKzA). Because what you want to do is implement a permutation via swaps. First, decompose the permutation into cycles (fast and easy), and then get the necessary swaps from each cycle. Won't help with the other edit operations, though – and mixing the two ain't trivial, I think.  

---

## 2 answers

### Answer by username_5 on 2012-06-22. Score: 2 | Accepted answer

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&B - easy](http://www.google.pl/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&ved=0CF8QFjAB&url=http://www.academic.marist.edu/~jzbv/algorithms/StudentProjects/BacktrackingandBandB.ppt&ei=ObXkT9rqI83ntQaStbz5CA&usg=AFQjCNHJFlUnnQjUemvLCbg5FL0QWzFdPw&sig2=R783eQNjhJQ-hMS-SeHyDg), [Something more thorough with common application](http://www.win.tue.nl/~mdberg/Onderwijs/Algoritmiek_Material/backtracking.pdf)) 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.

> **Comments:**
> **username_0**: Not exactly what I need, but it is something to think about. Thank you!  

---

### Answer by username_5 on 2012-06-22. Score: -1

I agree to username_2 comment - this seems like exacly this kind of problem. It is not simplified because after each swap we can perform another and another ... so in each step of the algorithm we have O(n^2) possible swaps.

It would be helpful if you could identify the application of this question - perhaps the question itself is ill-posed.

I would also appreciate if you could elaborate on the cost-metric you would like to use for swaps other than adjectant - would it still be = 1?

If you a sure that this is exactly what you want I could propose a following metaheuristic based on local search ([An accessible publication about local search and other metaheurestics](http://www.google.pl/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&ved=0CFQQFjAB&url=http://cs.gmu.edu/~sean/book/metaheuristics/Essentials.pdf&ei=mLbjT4zTFo-e-Qbaz7iTCg&usg=AFQjCNGA7zwoYBsB2X7GHl9FDl7RkbK4Yg&sig2=tdfEzqbCsUCBOoSugX2jvg)):

Define following:

neighbourhood (possible move) | size:

* swap | O(n^2)
* letter change | O(n\*alphabethSize)
* delete | O(n)
* insert | O(n\*alphabethSize)

Steps:

1. Try each move and evaluate the D-L distance of the new sequence to target sequence.
2. Chose best move.
3. Go back to 1.

Stop if you have the target sequence or there are no more moves that get you closer to it (local minimum).

Possible execution optimisations:

* don't consider letters that are not in target seqence
* candidate moves (see the .pdf)
* you could use the greedy version of local search - choose the first move that betters the distance to target sequence (much faster but more likely to produce worse results). Also remember to evaluate the moves in random order in this version.

Optimality guarantee: **none** this is a heurestic.

**Guys please justify downvoting if you can.**

> **Comments:**
> **username_0**: Thank you for this answer. It's not my downvote. I have updated my question, hope this will help.  

---

