0

start我有一个对象列表，其中每个对象都具有end以下属性：

Item 0:
Start: 1
End: 12

Item 1:
Start: 6
End: 3

Item 2:
Start: 12
End: 6

我想订购它们，以便新列表中的每个项目都start与end之前和之后的项目相匹配。

所以在这个例子中，它将是：

[Item 0] [Item 2] [Item 1]
[1   12] [12   6] [6    3]

整个列表是否颠倒都没关系。

还有 2 个像上面那样不相关的列表混合在一起，所以我必须形成 2 个新列表，它们将具有正确的顺序，如上所示。

我只是要开始“蛮力”实现它，所以做了很多查询来创建这些列表，但我想问是否有人可能有更优雅的方法来解决这个问题。我不确定这种问题有多普遍，但我记得以前见过这个，所以也许有一些模式可以解决这个问题。

4

2 回答 2

2

假设每个开始和结束都有完美的开始/结束匹配：

items_by_start = dict((i.start, i) for i in your_items)

ordered_items = [your_items[0]]
for _ in xrange(len(your_items)-1):
    ordered_items.append(items_by_start[ordered_items[-1].end])
于 2013-02-24T23:34:34.043 回答
1

对元素进行排序表明没有重复的项目。但是，对于重复start的 s 或ends，您必须更加小心（并且可能有多个解决方案）。该问题相当于在无向图的连通分量中找到欧拉路径，可以通过将每个 ( , ) 对视为图边来获得。startend

有足够多的例子来说明如何在网络上用 Python 实现它。请记住，它可以在 O(m) 时间内轻松完成，其中 m 是边数。

此外，当且仅当每个顶点都具有偶数度时，欧几里得路径才存在。如果图表中有许多组件，它仍然成立。

于 2013-02-25T00:12:43.747 回答