# Alternative to Hamming distance for permutations

I have two strings, where one is a permutation of the other. I was wondering if there is an alternative to Hamming distance where instead of finding the minimum number of substitutions required, it would find the minimum number of translocations required to go from string a to string b.

My strings are always of the same size and I know there are no errors/substitutions.

Example:

1 2 3 4 5
3 2 5 4 1


This would give me two:

3 2 5 4 1 (start)
-> 3 2 1 4 5
-> -> 1 2 3 4 5


If this is already implemented in R that would be even better.

• Looks like you want the edit-distance ( aka Levenshtein distance) ?
– Arnab
Oct 12, 2012 at 17:00
• Oct 12, 2012 at 19:13
• In your particular example where the characters of the string have an implied order, you might want to count inversions. en.wikipedia.org/wiki/Inversion_(discrete_mathematics)
– Joe
Oct 12, 2012 at 19:26
• It might be disingenuous to call all of those distance functions metrics, as many may not obey the triangle inequality. Oct 12, 2012 at 19:41
• By translocation do you mean taking the mirror image of part of the sequence? Oct 12, 2012 at 21:03

Finding the minimal distance is called the "Sorting By Translocation" problem. Part of an abstract from a paper:

"Given two signed multi-chromosomal genomes Pi and Gamma with the same gene set, the problem of sorting by translocations (SBT) is to find a shortest sequence of translocations transforming Pi to Gamma, where the length of the sequence is called the translocation distance between Pi and Gamma. In 1996, Hannenhalli gave the formula of the translocation distance for the first time, based on which an $O(n^3)$ algorithm for SBT was given. In 2005, Anne Bergeron et al. revisited this problem and gave an elementary proof for the formula of the translocation distance which leads to a new $O(n^3)$ algorithm for SBT."

What's called "translocation" here is called a transposition, i.e., a permutation of exactly two elements in a list, in traditional combinatorial language.

• This is exactly what I need! Do you happen to know of any working implementation, in either C or R? There doesn't seem to be one in the paper! Oct 14, 2012 at 0:50
• @user1357015 google it a bit and look through their references, I am sure you will find an implementation. I will also look. Also, note the last line which was added by someone - you might be looking for something a bit different, which is called "reversals". Pavel Pevzner has several papers on this. Oct 14, 2012 at 1:16
• @user1357015 found some python code here and this also might be helpful. Oct 14, 2012 at 3:51
• @Bitwise Note that Stack Overflow is the site you want to go to for actual code.
– Raphael
Oct 14, 2012 at 9:30

We need to find the minimum number of transpositions that take one string $$a$$ to another string $$b$$, where $$a, b$$ are permutations. It looks like you are looking for the minimum distance between two given vertices $$a, b \in S_n$$ in the complete transposition graph, which is the Cayley graph of $$S_n$$ generated by the set of all transpositions.