怎么度量一个排列相对于另一个排列的混乱程度？或者说相似度。

快乐勇敢的水手

有一个排列，比如[1、2、3、4、5]；
我要随机打乱它，比如得到[2、1、3、4、5]。
现在，我需要一个量来刻画排列2相对于排列1的混乱程度；或者说刻画两个排列的相似度，相似度越高，表明两个排列越接近。

目前我能想到的办法就是用宽度优先搜索来确定排列2位于排列1的第几层，层数越深表明相似度越低，混乱度越高。

但是具体运行起来发现这个办法很缓慢，尤其是排列比较长的时候（也可能跟我的算法实现有关）。

有没有一个什么统计学公式，把两个排列代进去就能很快速估算出一个相似度的值来，不太精确也行。

快乐勇敢的水手

或者是有其他好办法也行。请介绍介绍。

windoze

一共5个元素，取值范围1~5，你可以把它展开变成一个25维01向量，比如说12345就是00001 00010 00100 01000 10000，21345就是00010 00001 00100 01000 10000，然后算一下这两个向量的夹角的余弦，结果取值范围[1, -1]，但由于这个25维向量每一维取值只有0和1，也就是说都在第1象限，两个向量夹角不会大于90度，所以实际的取值范围是[1, 0]，1是最相似也就是完全一样，0是最不相似。

快乐勇敢的水手

回复 3# windoze


    谢谢猫兄，我试试。

cokeboL

谁都别拦着：猫哥是我偶像

windoze

回复 5# cokeboL

这个方法本来是用来计算文本串相似度的，在他这个问题里不一定适用，但我觉着拿来凑合一下应该是没问题的。

cokeboL

回复 6# windoze


    get                     

windoze

刚才拿python试了一下，感觉结果还是基本靠谱的，点积余弦之类的函数就直接用numpy了：

1. 
   
2. from numpy import (array, dot, arccos)
   
3. from numpy.linalg import norm
   
4. from random import shuffle
   
5. 
   
6. def to_vec(l, m):
   
7.         ret=[]
   
8.         for e in l:
   
9.                 sl=[0]*m
   
10.                 sl[e-1]=1
    
11.                 ret+=sl
    
12.         return ret
    
13. 
    
14. def sim1(u, v):
    
15.         return dot(u,v)/norm(u)/norm(v)
    
16. 
    
17. def sim(u, v, m):
    
18.         a=to_vec(u, m)
    
19.         b=to_vec(v, m)
    
20.         return sim1(a,b)
    
21. 
    
22. def test(n):
    
23.         a=list(range(1,n+1))
    
24.         b=list(range(1,n+1))
    
25.         shuffle(b)
    
26.         print a,
    
27.         print b,
    
28.         print "=>",
    
29.         print sim(a, b, n)
    
30. 
    
31. for n in range(10):
    
32.         test(5)
    
33. 
    
34. for n in range(10):
    
35.         test(10)
    

复制代码

输出结果：

1. 
   
2. [1, 2, 3, 4, 5] [1, 3, 2, 5, 4] => 0.2
   
3. [1, 2, 3, 4, 5] [2, 4, 5, 1, 3] => 0.0
   
4. [1, 2, 3, 4, 5] [1, 3, 2, 4, 5] => 0.6
   
5. [1, 2, 3, 4, 5] [3, 1, 5, 4, 2] => 0.2
   
6. [1, 2, 3, 4, 5] [1, 4, 2, 5, 3] => 0.2
   
7. [1, 2, 3, 4, 5] [3, 1, 5, 2, 4] => 0.0
   
8. [1, 2, 3, 4, 5] [3, 5, 2, 4, 1] => 0.2
   
9. [1, 2, 3, 4, 5] [1, 5, 4, 2, 3] => 0.2
   
10. [1, 2, 3, 4, 5] [1, 4, 2, 3, 5] => 0.4
    
11. [1, 2, 3, 4, 5] [4, 5, 3, 2, 1] => 0.2
    
12. [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] [2, 5, 6, 4, 10, 8, 7, 9, 3, 1] => 0.2
    
13. [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] [2, 9, 3, 5, 1, 8, 7, 6, 4, 10] => 0.3
    
14. [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] [5, 7, 4, 9, 3, 8, 6, 1, 2, 10] => 0.1
    
15. [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] [10, 4, 2, 6, 5, 1, 7, 9, 3, 8] => 0.2
    
16. [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] [7, 1, 8, 6, 4, 10, 2, 3, 9, 5] => 0.1
    
17. [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] [7, 3, 8, 5, 10, 6, 9, 1, 4, 2] => 0.1
    
18. [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] [10, 6, 8, 2, 9, 7, 4, 5, 1, 3] => 0.0
    
19. [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] [2, 4, 5, 8, 1, 10, 6, 7, 3, 9] => 0.0
    
20. [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] [3, 4, 7, 9, 10, 1, 8, 6, 2, 5] => 0.0
    
21. [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] [2, 9, 1, 7, 10, 6, 4, 8, 3, 5] => 0.2
    

复制代码

fender0107401

1 2 3
3 2 1

是同等混乱吗？顺序重要吗？

windoze

回复 10# fender0107401

lz不是说估算么，而且他也觉得相似度可以拿来凑合一下。

实际要想评估“混乱程度”你得做随机性测试，基本思路就是拿一大堆结果看分布，成本太高了。