Python: sắp xếp danh sách phụ thuộc

Question

Tôi đang cố gắng giải quyết nếu sự cố của tôi có thể giải quyết bằng hàm được sắp xếp() hoặc nếu tôi cần làm - trường cũ sử dụng cmp sẽ tương đối dễ.

dữ liệu thiết lập của tôi trông giống như:

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

Nguyên tắc phân loại nên về cơ bản cho tất cả các giá trị của N & Y trong đó Y> N, x [N] [0] không trong x [Y] [ 1]

Mặc dù tôi đang sử dụng Python 2.6, nơi đối số cmp vẫn có sẵn Tôi đang cố gắng làm cho Python 3 an toàn.

Vì vậy, điều này có thể được thực hiện bằng cách sử dụng một số phép thuật lambda và đối số chính không?

- == CẬP NHẬT == -

Cảm ơn Eli & Winston! Tôi đã không thực sự nghĩ rằng việc sử dụng chìa khóa sẽ làm việc, hoặc nếu tôi có thể nghi ngờ nó sẽ là một giải pháp còi giày mà không phải là lý tưởng.

Vì vấn đề của tôi là phụ thuộc vào bảng cơ sở dữ liệu, tôi phải bổ sung thêm mã của Eli để xóa một mục khỏi danh sách phụ thuộc của nó (trong cơ sở dữ liệu được thiết kế tốt, điều này sẽ không xảy ra.

giải pháp của tôi trên thế giới):

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

Điều bạn muốn được gọi là topological sort. Trong khi nó có thể thực hiện bằng cách sử dụng built-in sort(), nó khá là khó xử, và nó tốt hơn để thực hiện một loại topo trực tiếp trong python.

Tại sao nó sẽ khó xử? Nếu bạn nghiên cứu hai thuật toán trên trang wiki, cả hai đều dựa vào một tập hợp "nút được đánh dấu" đang chạy, một khái niệm khó có thể sử dụng trong một hình thức sort() có thể sử dụng, kể từ key=xxx (hoặc thậm chí cmp=xxx) hoạt động tốt nhất với chức năng so sánh không trạng thái , đặc biệt là vì timsort không đảm bảo thứ tự các phần tử sẽ được kiểm tra. Tôi (chắc chắn) chắc chắn rằng bất kỳ giải pháp nào mà sử dụng sử dụng sort() sẽ kết thúc việc tính toán một số thông tin cho mỗi cuộc gọi đến chức năng khóa/cmp , để giải quyết vấn đề phi trạng thái.

Sau đây là alg Tôi đã sử dụng (để sắp xếp một số dependancies thư viện javascript):

chỉnh sửa: làm lại này rất nhiều, dựa trên giải pháp Winston Ewert của

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 

---

Sidenote: nó là có thể để giày-horn một hàm cmp() thành key=xxx, như được nêu trong bộ theo dõi lỗi python message.

Answer 2

Qua tìm định dạng xấu và kỳ lạ Set loại hình này ... (tôi đã giữ chúng như các bộ và phân định các mục danh sách một cách chính xác ...) ... và sử dụng thư viện networkx để tạo thuận lợi cho việc ...

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

tôi làm một cái gì đó loại topo như thế này:

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 

Tôi nghĩ rằng nó đơn giản hơn phiên bản Eli của nhiều hơn một chút, tôi không biết về tính hiệu quả.

Answer 4

Đây là đề nghị của Winston, với một sợi dây và một tinh chỉnh nhỏ, đảo ngược dependencies.issubset(provided) với provided.issuperset(dependencies). Thay đổi đó cho phép bạn vượt qua dependencies trong mỗi cặp đầu vào dưới dạng một vòng lặp tùy ý thay vì nhất thiết phải là set.

Trường hợp sử dụng của tôi liên quan đến dict có khóa là các chuỗi mục, với giá trị cho mỗi khóa là list của tên mục mà khóa đó phụ thuộc. Khi tôi đã thiết lập rằng dict không trống, tôi có thể chuyển số iteritems() của mình sang thuật toán đã sửa đổi.

Một lần nữa xin cảm ơn Winston.

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