哪些算法可以根據歷史

Question

• 排名表有N個獨特的項目。
• 有K排序的列表，每個列表包括項目的一小部分，每個列表中不包含同一項目多次。
• 輸入是未排序的項目列表。
• 該算法應該基於K排序列表排序列表。

下面是一個例子：

• 有100個項目：項目1，項目2，...，item100
• 有一些可用的等級列表：列表1：項目1>項目2> Item12，列表2 ：Item12> item93> Item7，項目list3：Iterm1>項目3> Iterm97，List4：Iterm1> Iterm7>項目2

的輸入是：Iterm1，項目2，Iterm7和Item98。該算法應該根據這些列表對輸入進行排序。

在學習機方面我要尋找基於訓練組項目的許多部分有序列表，可以預測的項目列表（AKA活動列表）的「正確」的順序的算法，每個部分有序的項目列表可能包含活動列表不包含的其他項目。

Answer 1

構建有向非循環圖（DAG）與輸入元件作爲節點和從Itemi和Itemj限定邊緣當且僅當Itemi Itemj之前立即出現在一些列表中。然後，您可以通過在DAG上執行topological sort來獲得所需的訂單。

Answer 2

我想你的意思是排序列表定義偏序，是嗎？即如果Item1出現在其中一個列表中的Item2之前，則應將其視爲「較大」。

如果這是正確的，而不是要走的路是在一個更方便的形式，例如首先代表本一個矩陣M，這樣M[1][2]==1如果Item1在列表之一的Item2之前。然後我們有一個簡單的比較函數：

if M[X][Y] == 1: 
    return 1 # X > Y 
elif M[Y][X] == 1: 
    return -1 # Y > X 
else 
    return 0 # the elements are not comparable 

我們現在可以根據這個比較器對輸出進行排序。

在排序之前，您可能希望在此矩陣上運行傳遞閉包（Warshall算法），例如，如果列表Item1> Item3和Item3> Item2，但沒有列出Item2將與Item1一起出現的列表。傳遞閉包允許從兩個列表中推出Item1應該在Item2之前。

Answer 3

我會根據輸入組合一個加權圖（A> B之間的鏈接數是權重），將它放入一個N * N矩陣中，並在矩陣上執行冪迭代（GIYF）。