파이썬에서이 작업을 수행하는 가장 좋은 방법은 무엇입니까?

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 개 만들어야합니다. 그러면 위의 그림과 같이 올바른 순서가 지정됩니다.

나는 "brute-force"를 구현하여 이러한 목록을 작성하기 위해 많은 쿼리를 수행하기 시작할 것이지만 누군가가이 문제를 해결할 더 우아한 방법이 있는지 물어보고 싶다. 나는 이런 종류의 문제가 얼마나 흔한 지 잘 모르겠지만 전에 이것을 보았던 기억이있다. 아마도이 문제를 다루는 패턴이있을 것이다. 요소 중복 항목을 제시하지 주문

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 1

. 그러나 start 또는 end이 중복되면 더주의해야합니다 (둘 이상의 솔루션이 가능할 수도 있음). 문제는 각 (start,) 쌍을 그래프 가장자리로 처리하여 얻을 수있는 무향 그래프의 connected components에서 Eulerian paths을 찾는 것과 같습니다.

웹에서 파이썬으로 구현할 수있는 방법에 대한 충분한 예가 있습니다. O (m) 시간에 쉽게 끝낼 수 있다는 것을 명심하십시오. 여기서 m은 가장자리의 수입니다.

또한 유클리드 경로는 모든 꼭지점이 짝수 일 경우에만 존재합니다. 그래프에 많은 구성 요소가 있으면 여전히 보유합니다.

Answer 2

: 완벽하게 일치의 각각의 시작과 끝을위한 시작/종료에 대한 UPS가 가정