string transposition algorithm

Suppose there is given two String:

String s1= "MARTHA"
String s2= "MARHTA"

here we exchange positions of T and H. I am interested to write code which counts how many changes are necessary to transform from one String 开发者_如何学Cto another String.

---

There are several edit distance algorithms, the given Wikipeida link has links to a few.

---

Assuming that the distance counts only swaps, here is an idea based on permutations, that runs in linear time.

The first step of the algorithm is ensuring that the two strings are really equivalent in their character contents. This can be done in linear time using a hash table (or a fixed array that covers all the alphabet). If they are not, then s2 can't be considered a permutation of s1, and the "swap count" is irrelevant.

The second step counts the minimum number of swaps required to transform s2 to s1. This can be done by inspecting the permutation p that corresponds to the transformation from s1 to s2. For example, if s1="abcde" and s2="badce", then p=(2,1,4,3,5), meaning that position 1 contains element #2, position 2 contains element #1, etc. This permutation can be broke up into permutation cycles in linear time. The cycles in the example are (2,1) (4,3) and (5). The minimum swap count is the total count of the swaps required per cycle. A cycle of length k requires k-1 swaps in order to "fix it". Therefore, The number of swaps is N-C, where N is the string length and C is the number of cycles. In our example, the result is 2 (swap 1,2 and then 3,4).

Now, there are two problems here, and I think I'm too tired to solve them right now :)

1) My solution assumes that no character is repeated, which is not always the case. Some adjustment is needed to calculate the swap count correctly.

2) My formula #MinSwaps=N-C needs a proof... I didn't find it in the web.

---

Your problem is not so easy, since before counting the swaps you need to ensure that every swap reduces the "distance" (in equality) between these two strings. Then actually you look for the count but you should look for the smallest count (or at least I suppose), otherwise there exists infinite ways to swap a string to obtain another one.

You should first check which charaters are already in place, then for every character that is not look if there is a couple that can be swapped so that the next distance between strings is reduced. Then iterate over until you finish the process.

If you don't want to effectively do it but just count the number of swaps use a bit array in which you have 1 for every well-placed character and 0 otherwise. You will finish when every bit is 1.