부분적으로 주문한 목록을 정렬하는 가장 좋은 방법은 무엇입니까?

Question

아마도 작은 예로 가장 잘 설명 될 것입니다.
관계가 주어졌습니다

A < B < C
A < P < Q 

올바른 출력이 될 것입니다

ABCPQ or APQBC or APBCQ ... etc.

다시 말해, 모든 순서는 주어진 관계가 유지되는 경우 유효합니다.

구현하기가 가장 쉬운 솔루션에 가장 관심이 있지만 속도와 시간의 최고의 O (N)도 흥미 롭습니다.

Answer 1

이것은 ... 불리운다 토폴로지 분류.

표준 알고리즘은 최소한의 요소를 출력 한 다음 제거하고 완료 될 때까지 반복하는 것입니다.

Answer 2

여러 종류를 수행하십시오. 첫 번째 규칙에 따라 첫 번째 정렬, 두 번째 규칙에 따라 정렬됩니다. 규칙에 모순이 포함되지 않는 한 작동해야합니다. 구현하기에 충분히 쉽습니다.

Answer 3

당면한 시퀀스와 함께 c ++로 make_heap, pop_heap을 반복적으로 호출 할 수 있습니다.