Tim*_*lds 142
您只需计算列表中的反转次数即可.
逆温
类型元素序列中的反转T是一对序列元素,它们根据<集合上的某些排序而无序出现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
- 在这个SO问题中有几个有趣的方法:http://stackoverflow.com/questions/6523712/calculating-the-number-of-inversions-in-a-permutation基本上,它们相当于对数组进行排序以便弄清楚有多少倒置. (5认同)
- 我天真地以为你可以算一下乱序的相邻对.但这将严重低估:1 2 3 1 2 3只有一个相邻的反转,但它的50%被更正确的度量反转. (4认同)
- 对我来说,排序列表(通常)是O(n*logn),并且计算反转的天真/显而易见的方法是O(n ^ 2),这是很有趣的.我想知道是否有更好的算法来计算反演次数？ (2认同)
- @Barmar我认为列表1 2 3 1 2 3可以作为sorta排序;-) (2认同)
- @TimothyShields，嗯，不，不是。但是我不会太在意这一点。只是建议添加一个非正式的定义，该定义对于较少的符号倾向更易于使用。 (2认同)
- @BenFletcher重复的配对确实存在任何问题。重要的是彼此独立选择一对。对于较小的列表，您可以详尽地查看每对可能的组合，并且速度仍然非常快。对于较大的列表，包含重复项或不包含重复项之间的收敛速度差异可忽略不计。 (2认同)
Mar*_*cin 24
对列表(或其他顺序结构)进行排序的传统度量是反转次数.
反转次数是a <b AND b <<a 的对(a,b)st索引的数量.出于这些目的,<<表示您为特定排序选择的任何排序关系.
完全排序的列表没有反转,完全反转的列表具有最大的反转次数.
- @paxdiablo这取决于`<`的定义. (7认同)
- 从技术上讲,"5 4 3 2 1"完全排序,因为没有指定顺序,但我是迂腐:-) (5认同)
Kaz*_*Kaz 17
您可以使用实际关联.
假设对于排序列表中的每个项目,您指定从零开始的整数排名.请注意,元素位置索引与排名的关系图看起来像直线上的点(位置和排名之间的相关性为1.0).
您可以计算此数据的相关性.对于反向排序,您将获得-1,依此类推.
- 您需要排序列表来分配整数; 那么它只是项目的枚举. (2认同)
- 是的,只是Spearman的rho http://en.wikipedia.org/wiki/Spearman's_rank_correlation_coefficient (2认同)
有很好的答案，我想添加一个数学方面的完整性：
您可以通过测量列表与排序列表的相关程度来测量列表的排序程度。为此，您可以使用秩相关（最著名的是Spearman 相关），它与通常的相关完全相同，但它使用列表中元素的秩而不是其项目的模拟值。
存在许多扩展，例如相关系数（精确排序为+1，精确反转为-1）
这允许您具有此度量的统计属性，例如置换中心极限定理，它允许您了解随机列表的此度量的分布。