部分序排序？
假设我们有一些项目，每个项目都有一些部分排序的规则，比如：
我是
A，我想排在B前面。我是
C，我想排在A后面，但在D前面。
所以我们有项目 A,B,C,D，它们的规则是：
A>B（A在B前面）C<A（C在A后面），C>D（C在D前面）- 没有其他规则！所以，
B和D在排序上没有“偏好”，被视为相等。
如你所见，传递关系规则在这里并不适用。不过，如果 A>B，那也意味着 B<A。因此，排序的结果可能有多种可能性：
- A B C D
- A C D B
- A C B D
- A B C D
我该如何实现一个能够处理这种情况的排序算法呢？
原因是：有多个可加载的模块，其中一些模块在某种程度上“依赖”于其他模块。每个模块可以声明相对于其他模块的简单规则：
在模块 A 之前加载我
在模块 B 之后加载我
在模块 A 之前但在模块 B 之后加载我
现在我需要以某种方式实现这种排序.. :)
答案：代码来自 Paddy McCarthy（麻省理工学院）
## {{{ 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/ }}}
2 个回答
0
接下来会返回一个字典，里面的值是数字：
把它们按从大到小的顺序列出来，就能得到想要的结果
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