What is the best way to sort a partially ordered l

问题:

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.

回答1:

This is called topological sorting.

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

回答2:

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.

回答3:

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