What is the best way to sort a partially ordered l

Question

Probably best illustrated with a small example.
Given the relations

A < B < C
A < P < Q 

Correct outputs would be

ABCPQ or APQBC or APBCQ ... etc.

In other words, any ordering is valid in which the given relationships hold.

I am most interested in the solution that is easiest to implement, but the best O(n) in speed and time is interesting as well.

Answer 1

Do several sorts. First sort according to the first rule, then according to the second one and so on. Should work, unless your rules contain contradictions. sure easy enough to implement.

Answer 2

This is called topological sorting.

The standard algorithm is to output a minimal element, then remove it and repeat until done.

Answer 3

You could repeatedly call make_heap, pop_heap in C++ with the sequence at hand.