我如何从一组项目中形成一个平面的、有序的列表,每个项目都可能要求它们出现在列表中其他项目之前和/或之后?
Sample input
-----------------------
3: before 5 and after 2
8: before 5
2: before 3
5: no constraint
Sample output
-------------
[2, 3, 8, 5]
显然,这类问题的一般解决方案是非唯一的(考虑很多元素没有约束的情况),这很好 - 任何满足约束的结果都可以。
我也知道这里有很多错误情况(重复元素,两个元素都想在彼此之前,等等)。现在我对“快乐之路”感兴趣 - 我稍后会添加错误处理。
这里有一些 Python 测试用例。它们远非全面,但应该足以让您了解:
def test_some_unconstrained_elements():
l = ListBuilder()
l.add(1, after=None, before=None)
l.add(7, after=None, before=None)
assert set(l.to_list()) == {1, 7}
def test_element_which_should_appear_after_already_added_element():
l = ListBuilder()
l.add(5, after=None, before=None)
l.add(3, after=5, before=None)
assert l.to_list() == [5, 3]
def test_element_which_should_appear_after_element_added_later():
l = ListBuilder()
l.add(3, after=5, before=None)
l.add(5, after=None, before=None)
assert l.to_list() == [5, 3]
def test_element_which_should_appear_between_two_already_added_elements():
l = ListBuilder()
l.add(4, after=None, before=None)
l.add(2, after=None, before=None)
l.add(6, after=2, before=4)
assert l.to_list() == [2, 6, 4]
def test_two_elements_either_side_of_new_element():
l = ListBuilder()
l.add(4, after=6, before=None)
l.add(2, after=None, before=6)
l.add(6, after=None, before=None)
assert l.to_list() == [2, 6, 4]
def test_element_which_should_appear_after_missing_element():
l = ListBuilder()
l.add(4, after=6, before=None)
assert l.to_list() == [4]
def test_two_elements_which_should_appear_after_the_same_element():
l = ListBuilder()
l.add(4, after=None, before=None)
l.add(6, after=4, before=None)
l.add(8, after=4, before=None)
assert l[0] == 4
assert set(l[1:]) == {6, 8}
def test_fully_constrained_short_list():
l = ListBuilder()
l.add(3, after=4, before=None)
l.add(4, after=5, before=3)
l.add(5, after=None, before=4)
assert l.to_list() == [5, 4, 3]
注意。 这不是作业。这是我在现实生活中需要解决的实际问题(我正在研究 a test framework ;我很乐意详细说明我需要它做什么),但我还不够聪明:(
最佳答案
这看起来像是一种拓扑排序,所以从某个地方(例如 here)获取一个实现并修改您的数据格式以使用它。例如:
def toposort2(data):
# modified from http://rosettacode.org/wiki/Topological_sort#Python
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
for x in sorted(ordered):
yield x
data = {item: (dep - ordered) for item,dep in data.items()
if item not in ordered}
if data:
raise ValueError("a cyclic dependency exists")
def toposort_wrap(data):
dep_dict = {}
for d in data:
for bef in d.get("before", ()):
dep_dict.setdefault(bef, set()).add(d["value"])
dep_dict.setdefault(d["value"], set()).update(d.get("after", ()))
print dep_dict
result = list(toposort2(dep_dict))
return result
之后我们有
>>> data = [dict(value=3, before=(5,), after=(2,)),
... dict(value=8, before=(5,)),
... dict(value=2, before=(3,)),
... dict(value=5)]
>>> toposort_wrap(data)
{8: set([]), 2: set([]), 3: set([2]), 5: set([8, 3])}
[2, 8, 3, 5]
(未经测试,所以比其他任何东西都更多的概念验证,但这就是我的处理方式。)
关于python - 从元素之间的位置关系构建列表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21417848/