Каков наилучший способ сделать это в Python?

Question

У меня есть список объектов, где каждый из них имеют 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 новых списка, которые будут иметь правильный порядок, как показано выше.

Я только собираюсь начать реализацию этого «грубой силы», так что много запросов для создания этих списков, но я хотел спросить, есть ли у кого-то более элегантный способ решить эту проблему. Я не уверен, насколько распространена такая проблема, но я помню это раньше, так что, возможно, существуют шаблоны для решения этой проблемы.

Answer 1

Предполагая, что есть идеальный матч окна для запуска/окончания для каждого начала и конца:

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]) 

Answer 2

Заказ элементов не дает никаких повторяющихся элементов. Однако с дубликатом start s или end вы должны быть более осторожны (и может быть возможно несколько решений). Задача была бы равна обнаружению Eulerian paths в connected components неориентированного графа, который может быть получен путем обработки каждой пары (,) в виде края графика.

Существует более чем достаточно примеров того, как это можно реализовать в Python в Интернете. Имейте в виду, что это можно легко сделать в O (m) времени, где m - количество ребер.

Кроме того, евклидова траектория существует тогда и только тогда, когда каждая вершина имеет четную степень. Он по-прежнему сохраняется, если на вашем графике много компонентов.