假设有提供两个字符串：

Suppose there is given two String:

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

在这里我们交流T和H.我有兴趣写code，计数许多变化是如何需要从一个字符串转换到另一个字符串的位置。

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 to another String.

推荐答案

假设的距离只计算互换，这里是一个基于置换的想法，即以线性时间运行。

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

该算法的第一步是确保两个字符串是在他们的性格内容真是相当的。这可以在线性时间内使用散列表（或一个固定阵列，涵盖所有的字母）来完成。如果它们不是，则s2的不能被认为s1的一个置换，且交换计数是无关紧要的。

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.

第二步计数变换S2至S1需要互换的最小数目。这可以通过检查对应于变换从s1至s2中置P来完成。例如，如果s1 =ABCDE和s2 =badce，则p =（2,1,4,3,5），这意味着位置1包含元件＃2，位置2包含元素＃1等，这置换可以分裂成置换周期的线性时间。该示例中的周期是（2,1）（4,3）和（5）。最小交换次数是每个周期所需的所有掉期的总数。长度为k的周期需要K-1交换，以修复。因此，互换的数量是NC，其中N是字符串长度，C是周期数。在我们的例子中，结果是2（交换1,2-然后3,4）。

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）我的解决办法假定没有字符被重复，这并不总是如此。有些调整是需要正确地计算交换计数。

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）我的公式＃MinSwaps = NC需要证明......我没有找到它的网络。

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