有没有一种方法来衡量一个列表如何sorting?

有没有办法测量一个列表的sorting方式?

我的意思是,这不是要知道一个列表是否被sorting(布尔),而是像“sorting”的比率,就像统计中的相关系数一样。

例如,

  • 如果列表中的项目按升序排列,那么它的比率就是1.0

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

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

  • 如果列表根本没有sorting(随机),它的速率将接近于0

我正在斯卡拉的一个小型图书馆练习。 我认为sorting率是有用的,但我没有find任何关于这样的信息。 也许我不了解这个概念的充分条件。

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

逆温

Ttypes的元素序列中的反转是一对序列元素,它们按照T的集合上的一些sorting<顺序出现。

维基百科 :

正式地,令A(1), A(2), ..., A(n)n数字的序列。
如果i < jA(i) > A(j) ,则(i,j)对称为A反演

序列的倒数是其sorting的一个常用度量。
倒数定义为倒数的数量,也就是说,

定义

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

如果你想要一个介于01之间的值,你可以用N choose 2来除反转号码。

要实际创build一个algorithm来计算列表的sorting方式,您有两种方法:

方法1(确定性)

修改您最喜爱的sortingalgorithm,以跟踪它在运行时正在纠正的倒数。 尽pipe这是非常平凡的,并且根据您select的sortingalgorithm而有不同的实现,但您最终将得到的algorithm不会比开始使用的sortingalgorithm更昂贵(就复杂性而言)。

如果你采取这种方式,请注意,这不像计算“掉期”那么简单。 例如,Mergesort是最坏的情况O(N log N) ,但是如果它按照降序排列的列表运行,它将会纠正所有的N choose 2反转。 这是在O(N log N)操作中纠正的O(N^2)倒置。 所以有些操作必然要一次纠正一个以上的倒置。 你必须小心执行。 注意:你可以用O(N log N)复杂度来做到这一点,这只是一个棘手的问题。

相关: 计算置换中“倒数”的数量

方法2(随机)

  • 随机采样对(i,j) ,其中i != j
  • 对于每一对,确定list[min(i,j)] < list[max(i,j)] (0或1)
  • 计算这些比较的平均值,然后用N choose 2进行标准化, N choose 2

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


如果你真正想要的是-1 (sorting降序)到1 (sorting升序)之间的值( z' ),则可以简单地映射上面的值( z ),该值在0 (sorting升序)和1 (sorting降序),使用这个公式:

 z' = -2 * z + 1 

如何sorting列表(或其他顺序结构)的传统测量方法是反演次数。

倒数的数目是a <b AND b << a的对(a,b)st索引的数目。 为了这些目的, <<代表您为特定类别select的任何顺序关系。

一个完全sorting的列表没有倒序,完全颠倒的列表具有最大的倒序数目。

你可以使用实际的相关性。

假设对于sorting列表中的每个项目,您分配一个从零开始的整数sorting。 请注意,元素位置索引对等级的graphics看起来像一条直线上的点(位置和等级之间的相关性为1.0)。

您可以计算此数据的相关性。 对于反向sorting,您将得到-1等等。

有很好的答案,我想补充一个完整性的math方面:

  • 您可以通过测量与sorting列表相关的程度来衡量列表的sorting方式。 要做到这一点,你可以使用等级相关性(最着名的是Spearman's ),它与通常的相关性完全相同,但它使用列表中的元素排名而不是其项目的模拟值。

  • 存在许多扩展,如相关系数 (精确sorting+1,精确反转-1)

  • 这允许你有这个度量的统计特性,比如置换中心极限定理,它可以让你知道随机列表的这个度量的分布。

除了倒数计数之外,对于数字列表,可以想象从sorting状态到均值的平方距离:

 #! 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 

我不确定“最好”的方法,但一个简单的方法是比较每个元素和后面的元素,如果元素2>元素1(或任何你想testing的)增加一个计数器,然后除以总数的元素。 它应该给你一个百分比。

我会计数比较,并将其分为比较的总数。 这是一个简单的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 

这样的事情呢?

 #!/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() 

如果你拿你的清单,计算列表中的值的等级,并调用等级列表Y和另一个列表X ,包含从1length(Y)的整数,你可以精确地获得你所sorting的度量通过计算两个列表之间的相关系数 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}} 

对于完全sorting的列表, r = 1.0 ,对于逆sorting列表, r=-1.0 ,并且对于不同程度的sorting, r=-1.0在这些限制之间变化。

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