c++ - 排列之间的差异

Question

有没有办法定量计算两个排列之间的距离？

假设我们有以下两个元素序列:

A = {0, 1, 2, 3}
B = {0, 3, 2, 1}

我可以说排列 B不同于A因为:

• 我需要 1 交换操作才能转换 B至A
• B 中有 2 个元素A 中相同元素的索引不同

还有其他方法可以比较和描述两者之间的差异吗？

主要目标是定义一个能够逼近第二个排列的算法 B到第一个A ，这样，如果应用此过程的所有步骤，结果将是排列 A本身。 但为了做到这一点，我认为最好首先定义一个合理的程序来描述B的数量。不同于A .

是否有任何已知的算法允许接近另一个排列？

Answer 1

有几种不同的方法来定义两个序列之间的差异。仅举几例:

<强> Hamming distance :元素不同的位置数。

hamming(A, B)
  B[1] is different than A[1] and B[3] is different than A[3]
=> 2

<强> Levenshtein distance :从一个序列到另一个序列所需的最小修改次数。

levenshtein(A, B)
  replace B[1] with A[1] and replace B[3] with A[3]
=> 2

<强> Damerau–Levenshtein distance :前者的扩展，考虑了换位。

damerau_levenshtein(A, B)
  transpose B[3] with B[1]
=> 1

根据您给出的示例，您对跟踪换位感兴趣，因此 Damerau-Levenshtein 距离是您的最佳选择。