Quelle est la meilleure façon de trier une liste partiellement ordonnée?

Probablement le mieux illustré avec un petit exemple.
Compte tenu des relationsQuelle est la meilleure façon de trier une liste partiellement ordonnée?

A < B < C 
A < P < Q

sorties correctes seraient

ABCPQ or APQBC or APBCQ ... etc.

En d'autres termes, toute commande est valide dans lequel les relations données tiennent.

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

Source

2009-01-26 mike g

Demandez-vous un moyen de fusionner deux listes triées? – Triptych

Non, une seule liste initialement aléatoire –

Je n'ai toujours pas la question, désolé. Que voulez-vous dire par "au hasard"? Et si le résultat devait être trié, pourquoi avez-vous plusieurs résultats possibles (qui, pour moi, ne sont pas vraiment triés)? Un autre exemple plus long est-il possible? – Kosi2801

Ceci est appelé topological sorting.

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

Source

2009-01-26 18:32:16 starblue

Effectuez plusieurs opérations. Premier tri selon la première règle, puis selon la seconde et ainsi de suite. Devrait fonctionner, à moins que vos règles contiennent des contradictions. sûr assez facile à mettre en œuvre.

Source

2009-01-26 18:02:56 user54579

c'est juste un exemple - il n'y a pas que 2 règles en général –

Je ne suis pas sûr que le nombre de règles soit un problème. Le résultat sera toujours correct. un petit problème de performance peut-être. – user54579

et il est important d'être un tri stable –

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

Source

2009-01-26 18:55:46

Quelle est la meilleure façon de trier une liste partiellement ordonnée?

Répondre

Questions connexes