是否有一种有效的方法来测量两个排序数字/字母序列之间的相似性/距离。这两个序列的长度不同，只有一些相同的元素？
例如，如果我有三个这样的排序数字序列：
序列 A：1,2,3,4,5,6
序列 B：2,3,4,5,6,7,8,9,10
序列 C：6,3,4,2,5,8,7,10,9
直观地说，我猜序列 A 和 B 更相似，因为它们有更多的公共数字，并且公共数字在两个序列中具有相同的顺序。序列 A 和 C 不太相似，因为它们的公共数量较少，并且公共数字在每个序列中具有不同的顺序。Damerau-Levenshtein 距离似乎是一个不错的选择，它衡量两个字母串之间的相似性，考虑到字母的插入、删除、替换和相邻换位。但我也想考虑非相邻换位，即两个交换字母之间的两个字母。例如，在上面的序列 C 中，“2”和“6”被交换，但它们不是相邻的字母，因为它们之间有“3”和“4”。Damerau-Levenshtein 距离似乎没有考虑到这一点。
首先，我会使用将元素置于相同顺序的成本。当然，这忽略了缺失元素的插入。
一个简单的解决方案是插入排序：
6,3 move 3 1 ahead => cost 1.
3,6,4 move 4 1 ahead => cost 1+1.
3,4,6,2 move 2 3 ahead => cost 1+1+3.
2,3,4,6,5 move 5 1 ahead => cost 1+1+3+1.
2,3,4,5,6,8 correct => cost 1+1+3+1.
2,3,4,5,6,8,7 move 7 1 ahead => cost 1+1+3+1+1.
2,3,4,5,6,7,8,10 correct => cost 1+1+3+1+1.
2,3,4,5,6,7,8,10,9 move 9 1 ahead => cost 1+1+3+1+1+1=8.
算法复杂度为。
一种更有效的方法是使用关联映射预先计算每个元素的所需位置并计算距离。结果将与上述略有不同。
mapB={0: 2, 1: 3, ...}
cost( 6)=abs(4-0)=4
cost( 3)=abs(1-1)=0
cost( 4)=abs(2-2)=0
cost( 2)=abs(0-3)=3
cost( 5)=abs(3-4)=1
cost( 8)=abs(6-5)=1
cost( 7)=abs(5-6)=1
cost(10)=abs(8-7)=1
cost( 9)=abs(7-8)=1
total=12
使用有序映射（树），忽略旋转，将给出。使用哈希表，忽略冲突，将给出。
现在，我们必须处理缺失元素的插入。第二种算法允许我们计算存在于第二个序列中但不存在于第一个序列中的元素 ( seq2only)。如果我们消除/标记我们在第一个序列中遇到的元素，我们可以很容易地计算出第一个序列中存在的元素，但第二个序列中没有（seq1only）。对那些人的惩罚是insertioncost*(seq2only+seq1only)。