如何對這個「矩陣」數據進行排序？

Question

我運行的是一個體育網站，根據他們以前的會議將人員排在彼此之間通常很有用。

參見本實施例中設置的數據：

在左邊是原始 「未分類」 的說法。右側是正確排序的（在我看來）列表。

每個方塊顯示他們互相競爭的次數和勝利的百分比。他們根據百分比着色。

我在網頁上有這個，在每一行旁邊都有「向上」和「向下」的控件，我可以手動將它們四處移動，直到我得到我想要的。

我只是不確定自動執行此操作的最佳方法。

每行末尾的數字是我粗略出來的一個快速想法，並等於（百分比-50 *列號）行的總和。正如你所看到的，他們做得相當不錯，只有前兩行是「錯誤的」。他們沒有給予任何會議次數的重量，但只有贏的比例。

根據行順序，最終列數也會發生變化，這可以通過比較圖像中的左右表來看出，因此對初始值進行排序不會很好。循環排序+重新計算幾次就可以完成這項工作。

我希望我可以拼湊一些東西在一起，使這項工作...但我覺得所以這將有一些更好的想法，我會大聲耳朵。

Answer 1

A tournament是一個圖，其中每對頂點之間只有一個有向邊;從你的輸入中創建一個圖形，你可以爲每個玩家制作一個頂點的圖形，然後按照贏得大多數遊戲的玩家的方向「指向」兩個玩家之間的每個邊緣（你需要打破關係不知何故）。

如果你做到這一點，如果沒有周期A> B> ...>我在這個圖表註釋中提到的類型的，那麼該圖是傳遞，你可以訂購玩家使用圖的topological sort。這對於n個玩家來說只需要線性時間，即O（n^2）。

如果有是這樣的週期，那麼沒有「完美」的玩家排序：任何排序都會將至少一個玩家排在他們被擊敗的玩家之後。在這種情況下，合理的選擇是尋找最小化這些「邊緣違規」數量的排序。這在計算機科學中稱爲（最小）反饋弧集（FAST）中的一個研究得很深的NP難題。 A feedback arc set是一組有向邊（「弧」），如果從圖中刪除，則會留下一個沒有定向循環的圖 - 然後可以像以前一樣使用拓撲排序輕鬆轉換爲一個定單。

This paper描述了最近對該問題的攻擊。我沒有閱讀論文，但這是一個活躍的研究領域，所以這個算法可能相當複雜 - 但它可能會給你一些關於如何創建一個更簡單的算法的想法，該算法的運行速度較慢（但在這樣的小實例中速度可以接受），或者如何創建啓發式。

Answer 2

只要添加到j_random的答案，你可以使用像Tarjan's strongly connected components algorithm這樣的東西隔離週期。在強連通的組件中，可以使用其他方法對項目進行排序。