使用不完整的比較函數排序列表

我有一組對象，我需要生成一個排序列表，但是我的比較函數是不完整的，並且在排序算法部分留下了一些「想象力」空間。使用不完整的比較函數排序列表

具體地，給出的樹木像集合了以下內容：

 
    A  E 
    |  | 
    B--C F 
    | 
    D

我手邊是一組節點{A, B, C, D, E, F}的，沒有特定的順序，並測試直接父子關係的函數：

 
parent(A, B) 
parent(A, C) 
parent(B, D) 
parent(E, F)

我需要拼合到一個列表中的父母子女之前在那裏走到這一步，但除此之外，順序是不重要的。因此，這些結果是可以接受的：

 
A, B, C, D, E, F. 

A, B, D, C, E, F. 

E, F, A, B, C, D. 

A, E, B, C, F, D.

設定將會很小，最多幾十個，所以我不會太在意性能。我所關心的是避免列表以外的臨時數據結構：由於我使用的語言的限制，將這些項目組織到臨時樹中（例如）會令人不快。

來源

2009-12-19 Jesse McGrew

你可以使用這個簡單的算法：

while unsorted set is not empty { 
    elem = get element from unsorted set 
    while elem has parent and parent is in unsorted set { 
     elem = parent of elem 
    } 
    add elem to result list 
    remove elem from unsorted set 
}

來源

2009-12-19 15:20:38 tangens

對於沒有全局/共享狀態的算法+1：我正在使用的語言恰巧通過值傳遞列表（複製）。而且我確實有一個便宜的操作來查找元素的父項。 – 2009-12-19 16:12:18

或者，也許我不......那個操作可能會找到一個不在輸入集中的父類（我只考慮更大森林的一個子集），所以我必須搜索輸入集。 – 2009-12-19 16:15:22

我相信你正在尋找一個topological sort算法。

這裏是從維基百科文章的相關算法：

L ← Empty list that will contain the sorted nodes 
S ← Set of all nodes 

function visit(node n) 
    if n has not been visited yet then 
     mark n as visited 
     for each node m with an edge from n to m do 
      visit(m) 
     add n to L 

for each node n in S do 
    visit(n)

來源

2009-12-19 15:15:58 Amnon

該網頁上給出的深度優先搜索算法將slowish，因爲它要求您找到給定節點的所有父母的列表（在這種情況下，將需要檢查它們）。另一方面，根本不需要任何中間數據結構 - 只需遞歸函數調用 - 除非需要能夠檢測週期。 – 2009-12-19 15:22:50

@Jason：AFAICT您只需要節點的子節點列表，而不是父節點的列表。 – Amnon 2009-12-19 15:48:52

+1爲拓撲排序文章。我知道這個算法必須是常用的東西。 – 2009-12-19 16:08:39

使用不完整的比較函數排序列表

回答

相關問題