¿Cuál es la mejor manera de ordenar una lista parcialmente ordenada?

Question

Probablemente mejor ilustrado con un pequeño ejemplo.
Dadas las relaciones

A < B < C
A < P < Q 

Las salidas correctas serían

ABCPQ or APQBC or APBCQ ... etc.

En otras palabras, cualquier orden es válida en la que se mantienen las relaciones dadas.

Estoy más interesado en la solución que es más fácil de implementar, pero la mejor O (n) en velocidad y tiempo también es interesante.

Answer 1

Esto se llama clasificación topológica .

El algoritmo estándar es generar un elemento mínimo, luego eliminarlo y repetir hasta que esté listo.

Answer 2

Haz varios tipos. Primero ordena de acuerdo con la primera regla, luego de acuerdo con la segunda y así sucesivamente. Debería funcionar, a menos que sus reglas contengan contradicciones. seguro lo suficientemente fácil de implementar.

Answer 3

Puede llamar repetidamente a make_heap, pop_heap en C ++ con la secuencia a mano.