Sắp xếp thứ tự một phần?

Question

Say, chúng tôi có một số mặt hàng, và mỗi định nghĩa một số quy tắc phân loại từng phần, như thế này:

Tôi A và tôi muốn trở thành trước B

Tôi C và tôi muốn trở thành sau A nhưng trước khi D

Vì vậy, chúng tôi có các mục A,B,C,D với những quy tắc:

• A>B
• C<A, C>D
• không có gì khác! Vì vậy, B và D không có 'tùy chọn' theo thứ tự và được coi là bằng nhau.

Như bạn thấy, các quy tắc quan hệ chuyển tiếp không hoạt động ở đây. Tuy nhiên, nếu A>B nó vẫn có nghĩa là B<A. Vì vậy, có thể có nhiều kết quả có thể phân loại:

1. A B C D
2. A C D B
3. A C B D
4. A B C D

Làm thế nào tôi có thể thực hiện một thuật toán sắp xếp để xử lý một tình huống như vậy?

---

Lý do: có nhiều mô-đun có thể tải và một số phụ thuộc vào người khác theo cách. Mỗi module có thể tuyên bố quy tắc đơn giản, liên quan đến các module khác:

Tải tôi trước khi module A

Tải tôi sau khi mô-đun B

Tải tôi trước khi module A nhưng sau khi mô-đun B

bây giờ tôi cần phải thực hiện thứ tự này bằng cách nào đó .. :)

---

Trả lời: code bởi Paddy McCarthy (MIT)

## {{{ http://code.activestate.com/recipes/577413/ (r1) 
try: 
    from functools import reduce 
except: 
    pass 

data = { 
    'des_system_lib': set('std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee'.split()), 
    'dw01':    set('ieee dw01 dware gtech'.split()), 
    'dw02':    set('ieee dw02 dware'.split()), 
    'dw03':    set('std synopsys dware dw03 dw02 dw01 ieee gtech'.split()), 
    'dw04':    set('dw04 ieee dw01 dware gtech'.split()), 
    'dw05':    set('dw05 ieee dware'.split()), 
    'dw06':    set('dw06 ieee dware'.split()), 
    'dw07':    set('ieee dware'.split()), 
    'dware':   set('ieee dware'.split()), 
    'gtech':   set('ieee gtech'.split()), 
    'ramlib':   set('std ieee'.split()), 
    'std_cell_lib':  set('ieee std_cell_lib'.split()), 
    'synopsys':   set(), 
    } 

def toposort2(data): 
    for k, v in data.items(): 
     v.discard(k) # Ignore self dependencies 
    extra_items_in_deps = reduce(set.union, data.values()) - set(data.keys()) 
    data.update({item:set() for item in extra_items_in_deps}) 
    while True: 
     ordered = set(item for item,dep in data.items() if not dep) 
     if not ordered: 
      break 
     yield ' '.join(sorted(ordered)) 
     data = {item: (dep - ordered) for item,dep in data.items() 
       if item not in ordered} 
    assert not data, "A cyclic dependency exists amongst %r" % data 

print ('\n'.join(toposort2(data))) 
## end of http://code.activestate.com/recipes/577413/ }}} 

Answer 1

Bạn sẽ muốn xây dựng một dependency graph (mà chỉ là một hương vị của đồ thị có hướng), và sau đó làm theo một trật tự topologically sorted. Đã được một thời gian kể từ khi tôi tham gia một lớp tổ hợp, vì vậy bài viết trên Wikipedia có lẽ sẽ hữu ích hơn tôi vì một thuật toán sắp xếp topo. Tôi hy vọng cung cấp cho bạn các thuật ngữ thích hợp là hữu ích. :)

Theo như xây dựng biểu đồ, về cơ bản bạn chỉ cần có mỗi mô-đun với danh sách phụ thuộc của mô-đun đó.

Bạn chỉ cần lặp lại quy tắc của mình một chút ... "Tôi là C và tôi muốn sau A nhưng trước D" sẽ được biểu thị là "C phụ thuộc vào A" cũng như "D phụ thuộc trên C ", sao cho mọi thứ đang chảy theo hướng chuẩn.