排名相關算法

我有一個朋友的排名列表。然後，我再收到幾個同樣朋友的列表，但排名不同。是否有算法來檢查哪個列表與最初的排名列表最接近？排名相關算法

謝謝

2013-03-21 Mike

我想你可以通過使用[數組倒數算法]（http://stackoverflow.com/questions/337664/counting-inversions-in-array）在O（n日誌n）中運行。基本上，你把你原來的排名，你分配給每個項目一個ID遞增順序，然後你在「不同的排名」爲您的每個項目分配給他們相應的ID從初始排名（你應該能夠要有效地做到這一點），然後你應用我上面提到的算法分配給「不同排名」的ID。 – 2013-03-21 12:09:30

這可能取決於您對兩個排名之間「距離」的衡量標準。

例如，如果我們定義

dist(R1, R2) = Sum abs(position of i in R1 - position of i in R2), over all i

然後可以存儲在第一排名每i位置在陣列

即

pos[Peter] = 3

裝置那Peter顯示爲你的第三個朋友排行。

通過使用pos計算上述總和，可以在線性時間內找到最接近的排名。

來源

2013-03-21 14:53:08 abeln

這是一個很好的解決方案。然而，它並沒有告訴我很多關於距離的重要性。比方說，我有一個排名榜，有200個朋友排在第一位，另一方面，我有一個排名榜，其中一個朋友排名下了200個排名。距離將是相同的。然而，第二排名表比第一排名表要好得多。 – Mike 2013-04-02 23:01:55

您可以通過獲取位置差異的平方或立方體來懲罰較大的差異。 – abeln 2013-04-03 13:38:15

我想我可以。謝謝 – Mike 2013-04-05 12:27:13

我認爲你應該比較它們之間的等級距離，但使用權重。例如，如果用戶排名第一位在第十位，這是一個很大的差異，但如果用戶排名第101位在第110位，這不是一個大的變化。所以你應該對更高等級的用戶差異設置更高的係數。

來源

2013-03-21 15:55:08 aram90

排名相關算法

回答

相關問題