Сортировка частичного заказа?

Question

Скажем, у нас есть некоторые пункты, и каждый определяет некоторые частные правила сортировки, например:

Я A, и я хочу быть перед B

Я C и я хочу быть после того, как A но перед D

Таким образом, мы имеем элементы A,B,C,D с этими правилами:

• A>B
• C<A, C>D
• ничего! Таким образом, B и D не имеют никаких предпочтений при упорядочении и считаются равными.

Как вы видите, правила транзитивного отношения здесь не работают. Однако, если A>B все еще означает, что B<A. Таким образом, может быть несколько возможных результатов сортировки:

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

Как я могу реализовать алгоритм сортировки, который обрабатывает такую ​​ситуацию?

---

Причина: существует несколько загружаемых модулей, а некоторые из них «зависят» от других в некотором роде. Каждый модуль может объявить простые правила, по отношению к другим модулям:

Загрузите меня перед модулем А

Загружайте меня после того, как модуль B

Загружайте меня перед модулем A, но после того, как модуль B

сейчас мне нужно реализовать этот заказ как-то .. :)

---

Ответ: code Пэдди Маккарти (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

Вы хотите построить dependency graph (который является только ароматом ориентированного графа), а затем следует topologically sorted упорядочения. Прошло некоторое время с тех пор, как я взял класс комбинаторики, поэтому статья Википедии, вероятно, будет более полезна, чем для топологического алгоритма сортировки. Я надеюсь, что вам будет полезна правильная терминология. :)

Что касается построения графика, вам просто нужно будет иметь каждый модуль со списком зависимостей этого модуля.

Вам просто нужно немного перефразировать свои правила ... «Я C, и я хочу быть после A, но до D» будет выражаться как «C зависит от A», а также «D зависит на C ", так что все течет в стандартном направлении.