如何比较两个列表在多大程度上按相同顺序排列？

Question

我有两个包含相同元素但顺序不同的数组，我想知道它们的顺序差异程度。我尝试过一种方法，但并没有成功。具体方法如下：对于每个列表，我建立了一个矩阵，记录每对元素在列表中是上方还是下方。然后我计算了这两个矩阵的Pearson相关系数。结果非常糟糕。以下是一个微不足道的例子：

列表1： 1 2 3 4

列表2： 1 3 2 4

我描述的方法生成的矩阵如下（其中1表示行号高于列号，0表示反之）：

列表1： 1 2 3 4 1 1 1 1 2 1 1 3 1 4

列表2： 1 2 3 4 1 1 1 1 2 0 1 3 1 4

由于唯一的区别是元素2和3的顺序，因此应该认为它们非常相似。这两个矩阵的Pearson相关系数为0，表明它们根本没有相关性。我想问题在于我要寻找的不是相关系数，而是其他类型的相似度量。编辑距离，也许？有人能提供更好的建议吗？

- Ben

Answer 1

每个元素索引差的平方和。

List 1: A B C D E
List 2: A D C B E

在 List 2 中找到 List 1 中每个元素的索引（从0开始）

A B C D E
0 3 2 1 4

List 1中每个元素在List 1中的索引（从0开始计数）

A B C D E
0 1 2 3 4

区别：

A  B C D E
0 -2 0 2 0

差的平方：

A B C D E
  4   4

不同性的平均值 = 8/5。

- jamesh

---

当数组为(a,b,c,d,e)和(e,a,b,c,d)时，这个算法是如何工作的？这两个数组只有一个旋转的差异。但是上述算法将给出一个差异值为4 ((16+1+1+1+1)/5)。这是否符合原帖作者的意图？ - jmucchiello

那个单一的旋转将 e 移动到列表的另一端。对我来说，这似乎是一个合理的措施。 - recursive

Answer 2

只是一个想法，是否有价值将标准排序算法改编为计算将 list1 转换为 list2 所需的交换操作数量？

我认为定义比较函数可能会很困难（甚至可能与原问题一样困难！），而且这可能效率低下。

编辑：再考虑一下，比较函数本质上将由目标列表自身定义。例如，如果 list2 是：

1 4 6 5 3

...那么比较函数应该导致 1 < 4 < 6 < 5 < 3（并在条目相等时返回相等）。

然后只需要扩展交换函数以计算交换操作次数。

- frankodwyer

Answer 3

有点晚了，但仅供参考，我认为Ben几乎成功了...如果你进一步研究相关系数，你会发现Spearman等级相关系数可能是正确的选择。

有趣的是，jamesh似乎得出了类似的度量，但没有标准化。

请参见此最近的SO答案。

- bubaker

---

请查看此页面：Wiki-Spearman's_rank_corr_coef - JLT

请查看以下内容：或者查看此链接：https://www.statology.org/spearman-correlation-python/ - Ray

Answer 4

你可能需要考虑转换一个字符串成另一个字符串需要多少次变化（我猜你提到编辑距离时就是在谈论这个问题）。

参见：http://en.wikipedia.org/wiki/Levenshtein_distance

虽然我认为编辑距离并不考虑旋转。如果你允许旋转作为一种操作，那么：

1、2、3、4

和

2、3、4、1

非常相似。

- Dana

Answer 5

如果有人在使用R语言，我已经实现了一个函数，可以使用@bubake 这里描述的方法计算“斯皮尔曼等级相关系数”：

get_spearman_coef <- function(objectA, objectB) {
  #getting the spearman rho rank test 
  spearman_data <- data.frame(listA = objectA, listB = objectB)
  spearman_data$rankA <- 1:nrow(spearman_data) 
  rankB <- c()
  
  for (index_valueA in 1:nrow(spearman_data)) {
    for (index_valueB in 1:nrow(spearman_data)) {
      
      if (spearman_data$listA[index_valueA] == spearman_data$listB[index_valueB]) {
        rankB <- append(rankB, index_valueB)
      }
      
      
    }
  }
  spearman_data$rankB <- rankB
  spearman_data$distance <-(spearman_data$rankA - spearman_data$rankB)**2
  
  spearman <- 1 - ( (6 * sum(spearman_data$distance)) / (nrow(spearman_data) * ( nrow(spearman_data)**2 -1) ) )
  print(paste("spearman's rank correlation coefficient"))
  return( spearman)  
}

结果：

get_spearman_coef(c("a","b","c","d","e"), c("a","b","c","d","e"))

斯皮尔曼等级相关系数：1

get_spearman_coef(c("a","b","c","d","e"), c("b","a","d","c","e"))

斯皮尔曼等级相关系数：0.9

- E.loic

Answer 6

有一种分支定界算法，适用于任何您喜欢的运算符集。它可能不是非常快。伪代码大致如下：

bool bounded_recursive_compare_routine(int* a, int* b, int level, int bound){
    if (level > bound) return false;
    // if at end of a and b, return true
    // apply rule 0, like no-change
    if (*a == *b){
        bounded_recursive_compare_routine(a+1, b+1, level+0, bound);
        // if it returns true, return true;
    }
    // if can apply rule 1, like rotation, to b, try that and recur
    bounded_recursive_compare_routine(a+1, b+1, level+cost_of_rotation, bound);
    // if it returns true, return true;
    ...
    return false;
}

int get_minimum_cost(int* a, int* b){
    int bound;
    for (bound=0; ; bound++){
        if (bounded_recursive_compare_routine(a, b, 0, bound)) break;
    }
    return bound;
}

这个算法所需的时间大致是指数级的，因为它受到最后一个可行的边界的支配。

补充一下：这可以扩展到查找存储在trie中的最近匹配字符串。 我多年前在拼写校正算法中做过这件事。

- Mike Dunlavey

Answer 7

我不确定它在底层使用的确切公式，但是difflib.SequenceMatcher.ratio()正好可以做到这一点：

ratio(self) method of difflib.SequenceMatcher instance:
    Return a measure of the sequences' similarity (float in [0,1]).

代码示例：

from difflib import SequenceMatcher
sm = SequenceMatcher(None, '1234', '1324')
print sm.ratio()

>>> 0.75

- Deestan

Answer 8

另一种基于一点数学的方法是计算将一个数组转换为另一个数组所需的逆序对数量。一个逆序对是交换两个相邻数组元素。在Ruby中，可以这样做：

# extend class array by new method
class Array
  def dist(other)
    raise 'can calculate distance only to array with same length' if length != other.length
    # initialize count of inversions to 0
    count = 0
    # loop over all pairs of indices i, j with i<j
    length.times do |i|
      (i+1).upto(length) do |j|
        # increase count if i-th and j-th element have different order
        count += 1 if (self[i] <=> self[j]) != (other[i] <=> other[j])
      end
    end
    return count
  end
end
l1 = [1, 2, 3, 4]
l2 = [1, 3, 2, 4]
# try an example (prints 1)
puts l1.dist(l2)

长度为n的两个数组之间的距离可以在0（它们相同）和n *（n + 1）/ 2之间（将第一个数组反转得到第二个数组）。如果您希望始终将距离保持在0和1之间，以便比较不同长度的数组对的距离，请除以n *（n + 1）/ 2。

这种算法的缺点是其运行时间为n ^ 2。它还假设数组没有重复项，但可以进行调整。

关于代码行“count + = 1 if ...”的说明：只有当第一个列表的第i个元素小于其第j个元素且第二个列表的第i个元素大于其第j个元素或反之亦然时，计数才会增加（这意味着第一个列表的第i个元素大于其第j个元素且第二个列表的第i个元素小于其第j个元素）。简而言之：（l1 [i]＆lt; l1 [j] and l2 [i]＆gt; l2 [j]）or（l1 [i] > l1 [j] and l2 [i] < l2 [j]）

- jug

Answer 9

如果有两个订单，应该查看两个重要的排名相关系数：

1. 斯皮尔曼等级相关系数：https://en.wikipedia.org/wiki/Spearman%27s_rank_correlation_coefficient 这与Jamesh的答案几乎相同，但在范围为-1到1之间进行缩放。 它的定义为：
   1 - (6 * 平方距离之和) / (样本数 * (样本数**2 - 1))

2. 肯德尔tau系数：https://nl.wikipedia.org/wiki/Kendalls_tau

在使用Python时，可以使用以下代码：

 from scipy import stats

 order1 = [ 1, 2, 3, 4]
 order2 = [ 1, 3, 2, 4]
 print stats.spearmanr(order1, order2)[0]
 >> 0.8000
 print stats.kendalltau(order1, order2)[0]
 >> 0.6667

- JLT