如何對鏈接元組列表進行排序？

lst = [(u'course', u'session'), (u'instructor', u'session'), (u'session', u'trainee'), (u'person', u'trainee'), (u'person', u'instructor'), (u'course', u'instructor')]

我上面列出了元組，我需要用下面的邏輯對它進行排序.... 每個元組的第二個元素都依賴於第一個元素，例如，（當然，會話） - >會議是依賴於課程等..如何對鏈接元組列表進行排序？

我希望用他們依賴的優先級排序列表，少用或獨立的對象會首先所以輸出應該像下面，

lst = [course, person, instructor, session, trainee]

來源

2010-06-30 Avadhesh

你在尋找什麼叫做topological sort。維基百科頁面顯示了經典的Kahn和深度優先搜索算法; Python的例子是here（有點過時，但還是應該運行正常），對pypi（穩定和可重複使用 - 你也可以閱讀代碼在線here）和here（的Tarjan的算法，那種，也與依賴週期涉及指定），僅舉幾例。

來源

2010-06-30 05:42:01

從概念上講，您需要做的是創建一個由您的列表內容決定的邊的directed acyclic graph，然後在圖上執行topological sort。在Python的標準庫中不存在執行此操作的算法（至少不是我能想到的是我的頭頂），但是您可以在線找到大量第三方實現，例如http://www.bitformation.com/art/python_toposort.html

該網站的功能採用所有字符串的列表，items，以及字符串之間的另一對列表partial_order。您的lst應作爲第二個參數傳遞。要生成的第一個參數，你可以使用itertools.chain.from_iterable(lst)，所以整體的函數調用將

import itertools 
lst = ... 
ordering = topological_sort(itertools.chain.from_iterable(lst), lst)

或者你也可以從網站修改功能，只需要一個參數，並在圖中直接創建節點在您的lst中的值。

編輯：使用topsort模塊Alex Martelli鏈接到，您可以直接通過lst。

來源

2010-06-30 05:41:58

如何對鏈接元組列表進行排序？

回答

相關問題