Quel est le meilleur moyen de trier une liste partiellement ordonnée?

Question

Probablement mieux illustré par un petit exemple.
Compte tenu des relations

A < B < C
A < P < Q 

Les sorties correctes seraient

ABCPQ or APQBC or APBCQ ... etc.

En d'autres termes, tout ordre dans lequel les relations données sont respectées est valide.

Je suis très intéressé par la solution la plus facile à mettre en œuvre, mais le meilleur temps (n) O (n) en termes de temps et de vitesse est également intéressant.

Answer 1

Ceci s'appelle le le tri topologique .

L'algorithme standard consiste à sortir un élément minimal, puis à le supprimer et à le répéter jusqu'à la fin.

Answer 2

Faites plusieurs tris. Commencez par trier selon la première règle, puis selon la seconde et ainsi de suite. Devrait fonctionner, sauf si vos règles contiennent des contradictions. assez facile à mettre en œuvre.

Answer 3

Vous pouvez appeler à plusieurs reprises make_heap, pop_heap en C ++ avec la séquence en cours.