使用有限數據對非數字對象進行排序

Question

說我有時可以比較的非數字對象，但有時沒有用於比較的數據。

例如：

• A大於B更大，但不與之比較的C.
• B比C更大。

這清楚地創建了一個排序列表A，B,C。

但是，讓我們添加大於C的D。由於沒有比較D與A或B的數據，因此最終排名並不明確。

我在尋找的是一種用「盡力而爲」的方式來排列這些類型的數據點，知道數據有限，最終的排序列表只會被部分排序。

此外，我打算代表這不是一維數組。也許是某種樹？

另一個想法是將數據點與大量數據組合在一起，因爲它們可以很容易地排序。然後使用組間比較來對組進行排名。問題在於有時一個數據點可以與多個組進行比較。

Answer 1

如果我正確記得大學，這通常是用圖算法完成的。對邊緣從較大元素變爲較小元素的所有項目製作有向圖，並跟蹤節點有多少入局邊。從圖形中刪除沒有傳入邊的節點 - 減少刪除的節點指向的所有節點的傳入邊數 - 清洗，重複。有關詳細信息和算法提示，請致電topological sorting。

如果在任何時候你最終得到一個非空圖，其中所有節點都有一個入邊，那麼你的排序就有一個循環，因此不是一個排序。