Qual è il modo migliore per ordinare un elenco parzialmente ordinato?

Question

Probabilmente meglio illustrato con un piccolo esempio.
Date le relazioni

A < B < C
A < P < Q 

I risultati corretti sarebbero

ABCPQ or APQBC or APBCQ ... etc.

In altre parole, qualsiasi ordine è valido in cui valgono le relazioni date.

Sono molto interessato alla soluzione più semplice da implementare, ma anche la migliore O (n) in termini di velocità e tempo è interessante.

Answer 1

Questo si chiama ordinamento topologico .

L'algoritmo standard consiste nell'output di un elemento minimo, quindi rimuoverlo e ripetere fino al termine.

Answer 2

Esegui diversi tipi. Prima ordina secondo la prima regola, poi secondo la seconda e così via. Dovrebbe funzionare, a meno che le tue regole non contengano contraddizioni. sicuramente abbastanza facile da implementare.

Answer 3

Puoi chiamare ripetutamente make_heap, pop_heap in C ++ con la sequenza a portata di mano.