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

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

Мне 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

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

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


Ответ: 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/ }}}

person kolypto    schedule 06.01.2011    source источник


Ответы (2)


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

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

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

person Sapph    schedule 06.01.2011
comment
+1 Точно с терминологией. Существует множество реализаций Python (например, эта), если это необходимо. - person moinudin; 07.01.2011
comment
Очень помогло, спасибо! Однако это имеет мало общего с графами в его реализации. Логика такова: 0. создать пустой список sorted. 1. пройтись по списку, выбрать самый маленький элемент min(по сравнению со всеми остальными). Наименьших может быть несколько, выберите любой. 2. Добавить min к sorted 3. Если есть еще элементы — вернуться к 1 - person kolypto; 07.01.2011
comment
@o_O Tync Единственная разница в том, что ваша версия O(n^2), где «правильная» топологическая сортировка работает в O(E) (где E - количество ребер-зависимостей). Что касается связи с графами, вся ваша структура является графом, нравится вам это или нет :) - person Nikita Rybak; 07.01.2011
comment
NetworkX также реализует эту сортировку. - person Jochen Ritzel; 07.01.2011
comment
Нашел простую реализацию: logarithmic.net/pfh-files/blog/01208083168 /sort.py - person kolypto; 07.01.2011
comment
@o_O Тынк: Ух ты! очень хороший код, я думаю, вы должны опубликовать его как ответ, чтобы он не исчез, если сайт закроется (конечно, с правильной атрибуцией). - person Matthieu M.; 07.01.2011

Следующее вернет словарь с числом в качестве значений для переменных:

перечислите их в порядке убывания, чтобы получить требуемый результат

def sorter(var_str: str, the_list: list):
    '''
    1st Argument must be a STRING
        variables, seperated by commas(','),
        WITHOUT ANY SPACES
    Eg: if a, b, c, d are the variables:
            sorter('a,b,c,d', [...])    --> Allowed
            sorter('a, b, c, d', [...]) --> Not Allowed
            sorter('a b c d', [...])    --> Not Allowed

    2nd Argument must be LIST of STRINGS
        having the conditions which can only include
            variables mentioned in the 1st Argument
            seperated with > or = or <,
        WITHOUT ANY SPACES
    Eg: if the conditions are (a > b = c > e), (c > d):
            sorter('...', ['a>b=c>e', 'c>d']        --> Allowed
            sorter('...', ['a > b = c > e', 'c > d']--> Not Allowed
            sorter('...', ['a > b=c > e', 'c > d']  --> Not Allowed
    '''

    level, main_cond_list= {var: 0 for var in var_str.split(',')}, []

    for condition in the_list:
        # Separating conditions & vars
        cond_var = condition.replace('>', ' ').replace('=', ' ').replace('<', ' ').split()
        cond_oper, counter = [], 0
        for i in cond_var[:-1]:
            counter += len(i)
            cond_oper.append(condition[counter])
            counter += + 1

        # SPLITTING THE CORE-CONDITIONS INTO SMALLER ONES
        for id in range(len(cond_oper)):

            # for > operator
            if cond_oper[id] == '>':
                for sub in range(id, -1, -1):
                    if cond_oper[sub] in ['=', '>']:
                        main_cond_list.append(f"{cond_var[sub]} > {cond_var[id + 1]}")
                        continue
                    break

            # for < operator
            if cond_oper[id] == '<':
                for sub in range(id, -1, -1):
                    if cond_oper[sub] in ['=', '<']:
                        main_cond_list.append(f"{cond_var[id + 1]} > {cond_var[sub]}")
                        continue
                    break

            # for = operator
            if cond_oper[id] == '=':
                for sub in range(id, -1, -1):
                    if cond_oper[sub] in ['=']:
                        main_cond_list.append(f"{cond_var[sub]} = {cond_var[id + 1]}")
                        continue
                    break

#             ABOVE 24 lines can be written as below _ commented lines too
#             for signs, strng in [['>', '{cond_var[sub]} > {cond_var[id + 1]}'],
#                                  ['<', '{cond_var[id + 1]} > {cond_var[sub]}'],
#                                  ['=', '{cond_var[sub]} = {cond_var[id + 1]}']]:
#                 exec(f'''
# if cond_oper[id] == '{signs}':
#     for sub in range(id, -1, -1):
#         if cond_oper[sub] in ['=', '{signs}']:
#             main_cond_list.append(f"{strng}")
#             continue
#         break''')

    for i in set(main_cond_list):
        print(i)

    for main_condition in set(main_cond_list):
        var1, cond, var2 = main_condition.split()
        if cond == '>' and var1 < var2:
            level[var1] = level[var2]+1
        if cond == '=':
            level[var1] = level[var2]
        # ABOVE 5 lines can be written as below commented lines also
        # for i in ['', '+1']:
        #     exec(f'''level[{main_cond_list[0]}] {main_cond_list[1]} level[{main_cond_list[0]}[2]{i}''')

    return level
person Narayan Lahoti    schedule 03.08.2020
comment
Это форум для вопросов и ответов. Я не вижу вопроса в вашем сообщении. Пост также выглядит так, как будто он может быть домашним заданием для класса программирования. Если это так, вы все еще можете получать подсказки от пользователей здесь, но вам нужно будет задать вопрос. - person bsoist; 03.08.2020