163

有没有办法测量列表的排序方式？

我的意思是，这与知道列表是否已排序（布尔值）无关，而是类似于“排序”的比率，类似于统计中的相关系数。

例如，

  • 如果列表中的项目按升序排列，则其比率为 1.0

  • 如果列表按降序排序，则其速率将为 -1.0

  • 如果列表几乎按升序排序，则其速率将为 0.9 或接近 1 的某个值。

  • 如果列表根本没有排序（随机），它的比率将接近 0

我正在用 Scala 编写一个小型库以供练习。我认为分拣率会很有用，但我没有找到任何有关此类信息的信息。也许我不知道这个概念的适当术语。

4

9 回答 9

142

您可以简单地计算列表中的反转次数。

倒置

类型元素序列中的反转T是一对序列元素，根据's<集合上的某些排序出现乱序。T

来自维基百科：

形式上，让A(1), A(2), ..., A(n)是一个n数字序列。
如果i < j和A(i) > A(j)，则该对(i,j)称为的反转。A

序列的倒数是衡量其排序性的一种常用方法。
形式上，倒数被定义为倒数，即

定义

为了使这些定义更清楚，请考虑示例序列9, 5, 7, 6。这个序列有倒数 (0,1), (0,2), (0,3), (2,3)和倒数 4。

如果您想要一个介于0和之间的值1，您可以将反转数除以N choose 2。

要实际创建一个算法来计算列表的排序分数，您有两种方法：

方法 1（确定性）

修改您最喜欢的排序算法，以跟踪它在运行时纠正了多少反转。尽管这很重要，并且根据您选择的排序算法具有不同的实现，但您最终会得到一个不会比您开始使用的排序算法更昂贵的算法（就复杂性而言）。

如果您采取这条路线，请注意它并不像计算“掉期”那么简单。例如，Mergesort 是最坏的情况O(N log N)，但如果它在按降序排序的列表上运行，它将纠正所有N choose 2反转。这是在操作中O(N^2)纠正的反转。O(N log N)因此，某些操作不可避免地一次要纠正多个反转。你必须小心你的实施。注意：你可以用O(N log N)复杂的方法做到这一点，这很棘手。

相关：计算排列中“反转”的数量

方法 2（随机）

  • 随机抽样对(i,j)，其中i != j
  • 对于每一对，确定是list[min(i,j)] < list[max(i,j)](0 还是 1)
  • 计算这些比较的平均值，然后通过N choose 2

我个人会采用随机方法，除非你有精确性的要求——如果只是因为它很容易实现。

如果您真正想要的是（降序排序）到（升序排序）z'之间的值（ ：-11z01

z' = -2 * z + 1
于 2013-06-08T00:21:33.610 回答
24

The traditional measure of how sorted a list (or other sequential structure) is, is the number of inversions.

The number of inversions is the number of pairs (a,b) st index of a < b AND b << a. For these purposes << represents whatever ordering relation you choose for your particular sort.

A fully sorted list has no inversions, and a completely reversed list has the maximum number of inversions.

于 2013-06-08T00:15:53.700 回答
17

您可以使用实际相关性。

假设您为排序列表中的每个项目分配了一个从零开始的整数等级。请注意，元素位置索引与排名的关系图看起来像一条直线上的点（位置和排名之间的相关性为 1.0）。

您可以计算此数据的相关性。对于反向排序，您将得到-1，依此类推。

于 2013-06-08T00:48:52.790 回答
5

有很好的答案，我想添加一个数学方面的完整性：

  • 您可以通过测量列表与排序列表的相关程度来测量列表的排序程度。为此，您可以使用排名相关性（最著名的是Spearman's），它与通常的相关性完全相同，但它使用列表中元素的排名而不是其项目的模拟值。

  • 存在许多扩展，例如相关系数（+1 表示精确排序，-1 表示精确反转）

  • 这使您可以拥有此度量的统计属性，例如置换中心极限定理，它使您可以了解此度量对于随机列表的分布。

于 2013-06-12T07:14:53.660 回答
3

除了反转计数，对于数字列表，与排序状态的均方距离是可以想象的：

#! ruby
d = -> a { a.zip( a.sort ).map { |u, v| ( u - v ) ** 2 }.reduce( :+ ) ** 0.5 }

a = 8, 7, 3, 4, 10, 9, 6, 2, 5, 1
d.( a ) #=> 15.556
d.( a.sort ) #=> 0.0
d.( a.sort.reverse ) # => 18.166 is the worrst case
于 2013-06-08T00:52:24.137 回答
2

I am not sure of the "best" method, but a simple one would be to compare every element with the one after it, incrementing a counter if element2 > element 1 (or whatever you want to test) and then divide by the total number of elements. It should give you a percentage.

于 2013-06-08T00:14:47.850 回答
1

我会计算比较并将其除以比较总数。这是一个简单的Python示例。

my_list = [1,4,5,6,9,-1,5,3,55,11,12,13,14]

right_comparison_count = 0

for i in range(len(my_list)-1):
    if my_list[i] < my_list[i+1]: # Assume you want to it ascending order
        right_comparison_count += 1

if right_comparison_count == 0:
    result = -1
else:
    result = float(right_comparison_count) / float((len(my_list) - 1))

print result
于 2013-06-12T10:37:18.713 回答
0

如果您获取列表，计算该列表中值的等级并调用等级列表Y和另一个列表，X其中包含从1to的整数，您可以通过计算相关系数length(Y)来准确获得您正在寻找的排序度量, , 在两个列表之间。r

r = \frac{\sum ^n _{i=1}(X_i - \bar{X})(Y_i - \bar{Y})}{\sqrt{\sum ^n _{i=1}(X_i - \bar{X})^2} \sqrt{\sum ^n _{i=1}(Y_i - \bar{Y})^2}}

对于完全排序的列表，r = 1.0，对于反向排序的列表，r=-1.0，以及r这些限制之间的变化，用于不同程度的排序。

这种方法的一个可能问题是，根据应用程序，计算列表中每个项目的排名等同于对其进行排序，因此它是一个 O(n log n) 操作。

于 2013-06-08T00:23:57.150 回答
0

这样的事情怎么样？

#!/usr/bin/python3

def sign(x, y):
   if x < y:
      return 1
   elif x > y:
      return -1
   else:
      return 0

def mean(list_):
   return float(sum(list_)) / float(len(list_))

def main():
   list_ = [ 1, 2, 3, 4, 6, 5, 7, 8 ]
   signs = []
   # this zip is pairing up element 0, 1, then 1, 2, then 2, 3, etc...
   for elem1, elem2 in zip(list_[:-1], list_[1:]):
      signs.append(sign(elem1, elem2))

   # This should print 1 for a sorted list, -1 for a list that is in reverse order
   # and 0 for a run of the same numbers, like all 4's
   print(mean(signs))

main()
于 2013-06-08T01:52:35.827 回答