Частичная сортировка заказов? - PullRequest
Новая
       12

Частичная сортировка заказов?

15 голосов
/ 07 января 2011

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

Я 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

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

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

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

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

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

теперь мне нужно как-то реализовать этот порядок ..:)

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

1 Ответ

20 голосов
/ 07 января 2011

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

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

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

...