部分排序算法？

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

如何实现处理这种情况的排序算法？

---

原因：有多个可加载的模块，其中一些以某种方式“依赖”于其他模块。 每个模块可以声明相对于其他模块的简单规则：

在模块 A 之前加载我

在模块 B 之后加载我

在模块 A 之前但在模块 B 之后加载我

现在我需要以某种方式实现这种排序.. :)

---

答案：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/ }}}

- kolypto

Answer 1

您需要构建一个依赖图（这只是有向图的一种变体），然后按照拓扑排序的顺序进行操作。我已经很久没有上组合数学课了，所以维基百科文章对于拓扑排序算法可能比我更有帮助。我希望给您提供正确的术语是有帮助的。 :)

至于构建图形，您基本上只需要让每个模块都有该模块依赖项的列表即可。

您只需要稍微重新表达一下规则... "我是C，我想在A之后但在D之前"将被表示为"C依赖于A"以及"D依赖于C"，以使一切都按标准方向流动。

- Sapph

---

术语使用得非常准确。如果OP需要，有很多Python实现（例如这个）。 - moinudin

非常感谢您的帮助！然而，这与图形在其实现中几乎没有关系。逻辑是：0.创建一个空列表sorted。1.遍历列表，选择最小项min(与所有其他项进行比较)。可能有多个最小值，随意选择一个。2.将min添加到sorted中。3.如果还有更多项-回到1。 - kolypto

你的版本与“正确”的拓扑排序算法的唯一区别在于，你的版本时间复杂度为O(n^2)，而“正确”的拓扑排序算法的时间复杂度是O(E)（其中E是边或依赖关系的数量）。至于与图的关系，不管你是否喜欢，整个结构都是一个图。 - Nikita Rybak

NetworkX 也实现了这种排序方法。 - Jochen Ritzel

找到了一个简单的实现：http://www.logarithmic.net/pfh-files/blog/01208083168/sort.py - kolypto

@o_O Tync：哇！非常好的代码，我认为你应该将其发布为答案，这样即使网站关闭也不会消失（当然要适当署名）。 - Matthieu M.

Answer 2

以下代码将返回一个以数字为值的字典：

按降序排列以获得所需的输出

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

- Narayan Lahoti

---

这是一个问答论坛。我没有在你的帖子中看到问题。该帖子似乎也可能是编程课的作业。如果是，你仍然可以从这里的用户那里得到提示 - 但你必须提出一个问题。 - bsoist