我怎样才能从一组项目中形成一个扁平的、有序的列表,每个项目都可能有它们出现在列表中其他项目之前和/或之后的需求?你知道吗
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),并修改您的数据格式以使用它。例如:
之后我们有
(未经测试,因此比其他任何东西都更能证明概念,但我会这样做。)
拓扑排序似乎是一个很好的解决方案。图可以是这样的:列表中的每个元素都是节点。如果a在b之前,那么从b到a有一条定向边
相关问题 更多 >
编程相关推荐