Python：排序依賴列表

Question

我想解決如果我的問題是可以解決使用內置排序（）函數，或者如果我需要自己做 - 使用cmp的老學校本來會相對容易。

我的數據集看起來像：

 
x = [ 
('business', Set('fleet','address')) 
('device', Set('business','model','status','pack')) 
('txn', Set('device','business','operator')) 
.... 

排序規則應基本對於N & Y，其中Y> N，X [N] [0]不是在X [Y] [所有值1]

儘管我使用Python 2.6，其中cmp參數仍然可用，但我試圖讓這個Python 3安全。

那麼，這可以使用一些lambda魔術和關鍵參數來完成？

- == UPDATE == -

感謝禮&溫斯頓！我真的不認爲使用鑰匙會起作用，或者如果我能懷疑它會是一種不理想的鞋子喇叭解決方案。

因爲我的問題是數據庫表依賴關係，我不得不對Eli的代碼做一個小的添加，以便從它的依賴列表中刪除一個項目（在設計良好的數據庫中，這不會發生，但是誰住在那個神奇的完美世界）

我的解決方案：

def topological_sort(source): 
    """perform topo sort on elements. 

    :arg source: list of ``(name, set(names of dependancies))`` pairs 
    :returns: list of names, with dependancies listed first 
    """ 
    pending = [(name, set(deps)) for name, deps in source]   
    emitted = [] 
    while pending: 
     next_pending = [] 
     next_emitted = [] 
     for entry in pending: 
      name, deps = entry 
      deps.difference_update(set((name,)), emitted) # <-- pop self from dep, req Py2.6 
      if deps: 
       next_pending.append(entry) 
      else: 
       yield name 
       emitted.append(name) # <-- not required, but preserves original order 
       next_emitted.append(name) 
     if not next_emitted: 
      raise ValueError("cyclic dependancy detected: %s %r" % (name, (next_pending,))) 
     pending = next_pending 
     emitted = next_emitted 

Answer 1

你想要什麼叫做topological sort。雖然可以使用內置的sort()來實現，但它很尷尬，最好是直接在python中實現拓撲排序。

爲什麼它會變得尷尬？如果您在維基頁面上研究這兩種算法，則它們都依賴於一組正在運行的「標記節點」，由於key=xxx（或甚至cmp=xxx）對無狀態比較函數的效果最好，因此這個概念很難扭曲到sort()可以使用的形式，特別是因爲timsort不能保證元素將被檢查的順序。我（很漂亮）確定確實使用使用sort()的任何解決方案最終將冗餘計算每次調用key/cmp函數的一些信息，以解決無國籍問題。

以下是我一直在使用（一些JavaScript庫的依賴關係排序）ALG：

編輯：重新設計，這大大的基礎上，溫斯頓·尤爾特的解決方案

def topological_sort(source): 
    """perform topo sort on elements. 

    :arg source: list of ``(name, [list of dependancies])`` pairs 
    :returns: list of names, with dependancies listed first 
    """ 
    pending = [(name, set(deps)) for name, deps in source] # copy deps so we can modify set in-place  
    emitted = []   
    while pending: 
     next_pending = [] 
     next_emitted = [] 
     for entry in pending: 
      name, deps = entry 
      deps.difference_update(emitted) # remove deps we emitted last pass 
      if deps: # still has deps? recheck during next pass 
       next_pending.append(entry) 
      else: # no more deps? time to emit 
       yield name 
       emitted.append(name) # <-- not required, but helps preserve original ordering 
       next_emitted.append(name) # remember what we emitted for difference_update() in next pass 
     if not next_emitted: # all entries have unmet deps, one of two things is wrong... 
      raise ValueError("cyclic or missing dependancy detected: %r" % (next_pending,)) 
     pending = next_pending 
     emitted = next_emitted 

---

旁註：它是可能鞋號cmp()函數key=xxx，如在這個python bug跟蹤器message。

Answer 2

在尋找壞的格式和這個陌生的Set類型...（我已經把他們作爲元組和正確分隔列表項...）...並使用networkx庫來方便...

x = [ 
    ('business', ('fleet','address')), 
    ('device', ('business','model','status','pack')), 
    ('txn', ('device','business','operator')) 
] 

import networkx as nx 

g = nx.DiGraph() 
for key, vals in x: 
    for val in vals: 
     g.add_edge(key, val) 

print nx.topological_sort(g) 

Answer 3

我做一個拓撲排序是這樣的：

def topological_sort(items): 
    provided = set() 
    while items: 
     remaining_items = [] 
     emitted = False 

     for item, dependencies in items: 
      if dependencies.issubset(provided): 
        yield item 
        provided.add(item) 
        emitted = True 
      else: 
        remaining_items.append((item, dependencies)) 

     if not emitted: 
      raise TopologicalSortFailure() 

     items = remaining_items 

我認爲它是一個略多於利的版本簡單的，我不知道效率。

Answer 4

這是溫斯頓的建議，文檔字符串和一個微小的調整，與provided.issuperset(dependencies)。該更改允許您將每個輸入對中的dependencies作爲任意迭代來傳遞，而不一定是set。

我的用例涉及dict，其鍵是項目字符串，每個鍵的值都是該鍵所依賴的項目名稱的list。一旦我確定dict非空，我可以將其iteritems()傳遞給修改的算法。

再次感謝溫斯頓。

def topological_sort(items): 
    """ 
    'items' is an iterable of (item, dependencies) pairs, where 'dependencies' 
    is an iterable of the same type as 'items'. 

    If 'items' is a generator rather than a data structure, it should not be 
    empty. Passing an empty generator for 'items' (zero yields before return) 
    will cause topological_sort() to raise TopologicalSortFailure. 

    An empty iterable (e.g. list, tuple, set, ...) produces no items but 
    raises no exception. 
    """ 
    provided = set() 
    while items: 
     remaining_items = [] 
     emitted = False 

     for item, dependencies in items: 
      if provided.issuperset(dependencies): 
        yield item 
        provided.add(item) 
        emitted = True 
      else: 
        remaining_items.append((item, dependencies)) 

     if not emitted: 
      raise TopologicalSortFailure() 

     items = remaining_items