如果您有两个序列，一个是另一个序列的排列，如何测量两个序列之间的距离？
这篇文章的动机是上一篇关于统计的员额。对于某个词典，该帖子中使用的代码发现最长的语法对如下：
认证、整改
令人印象深刻，宽容
茶匙，茶匙
语法更有趣时，这两个词更不同，至少在我看来。
有几种方法可以衡量（不相似性）。上面前两对中的单词含义不同，但最后一对中的单词是同义词 [1]。上面的单词对与字符串没有太大区别。
很难量化两个词的含义有多不同，但更容易量化它们作为字符序列的不同程度。我们将看两种方法：汉明距离和换位距离。
您也可以喜欢：数学函数和转换数据类型在Groovy。
哈明距离
两个词之间的 Hamming 距离是它们不同的位置数。通过以固定宽度的字体查看上述单词，我们可以看到上述单词之间的 Hamming 距离。
certifications
rectifications
impressiveness
permissiveness
teaspoonsful
teaspoonfuls以上 Hamming 的距离为 2、5 和 4。
在我的字典中，最大哈明距离的语法是”不完美”和”完美主义”。（这些词是语法，有些诗意。Hamming 的距离是 13，因为这 13 个字母的单词在每个位置都不同。
imperfections
perfectionism换位距离
测量两个排列之间的距离的另一种方法是需要交换多少个元素才能将一个列表转换为另一个列表。这称为换位距离。例如，”认证”和”修正”之间的换位距离为 1，因为您只需交换第一个字符和第三个字符即可将一个字符转换为另一个字符。
“令人印象深刻的”和”宽容”之间的换位距离并不明显。通过实验，我们可以在距离上找到一个上限。这两个词在前五个字母中仅不同，因此”令人印象深刻的”和”放纵”之间的距离并不大于”不”和”permi”之间的距离。后一对单词的间隔不超过 4 个换位，如下序列所示：
impre
pmire
peirm
perim
permi但是，是否有较短的转位序列？如果我们使用其余字母”ssive”作为工作空间，这会有所帮助吗？
计算换位距离是很难的，就像NP硬。这是不幸的，因为换位有更多的实际应用，而不仅仅是文字游戏。例如，它被用于基因研究
请注意，换位距离允许交换任意两个元素。如果我们只允许交换连续元素，问题就容易多了，但结果并不相同。当限制为连续掉期时，”认证”和”修正”之间的距离为 3 而不是 1。我们可以交换”c”和”r”，把”cer”变成”rec”，所以我们必须做类似
cer
ecr
erc
rec我不知道允许旋转的距离的名称。”茶匙”和”茶匙”这两个词因一次旋转而不同，将”精”变为”ful”。虽然可以在一次旋转中完成此操作，但需要多次交换。
进一步阅读
[1] 虽然”茶匙”更常见，但我记得有一个学校教我们，这是不正确的。
我仍然对”法律兄弟”退缩，说”法律兄弟”;大多数人支持我。