donné 3 listes qui sont triés arbitrairement par le même ordre de tri inconnu. Existe-t-il un algorithme qui fusionne ces listes dans un qui est toujours trié par le même ordre?
Exemple:
list1: une b c F h
list2: b c e h
list3: c ré e f
Supposons que ces listes sont triées, mais l'ordre de tri utilisé n'est pas connu. Je tiens à combiner ces listes à un résultat qui ne contient pas de duplicats mais maintient toujours l'ordre de tri: une b c ré e F h
Comme indiqué ci-dessus: on sait que les listes données sont triées, mais on ne sait pas à quel ordre, mais l'exigence est que la liste fusionnée est toujours triée par la même commande (inconnue).
Dans l'exemple ci-dessus, je sais que l'élément "F" est positionné entre "E" et "H" car de la liste1, je sais que
"C" <"F" <"H",
de la liste2, je sais que
"C" <"E" <"H"
et de la liste3, je sais que
"E" <"F" et "C" <"E"
qui combine à:
"C" <"E" <"F" <"H"
Si l'ordre de tri ne peut être déterminé par aucune des listes données, il est permis de simplement ajouter l'élément à la fin de la liste des résultats. En outre, si l'ordre de tri d'une séquence d'éléments ne peut pas être déterminé, il est permis de les insérer dans n'importe quel ordre dans la liste tant qu'ils sont au bon endroit (par exemple, si je sais que "B" et "C" doit être inséré entre "A" et "D" mais je ne sais pas si cela devrait être ABCD ou ACBD, les deux sont admissibles.)
Bien sûr que ce n'est qu'un exemple. Les vraies listes sont plus longues (mais contiennent moins de 100 éléments), contiennent des éléments de caractères non célibataires mais multiples et l'ordre de tri n'est pas alphabétique. En outre, j'ai jusqu'à 5 listes.
J'ai besoin de mettre en œuvre cet algorithme à Delphi (et non: ce n'est pas des devoirs mais un problème de vie réel), mais je prends un algorithme dans une langue à condition que cela ne contienne pas trop de fonctions de bibliothèque magique ou complexes complexes.
La performance n'est pas une grande partie d'un problème, car cela se fait une fois.
5 Réponses :
La théorie du graphique semble être une bonne première intuition.
Vous pouvez créer un graphique dirigé lorsque les éléments de votre liste sont les sommets et vous insérez un bord dirigé de chaque élément de liste à son successeur. Ensuite, un nœud A est moins que un autre noeud B si et uniquement si B peut être atteint à partir d'un en traversant le graphique.
Un cycle dans le graphique (A est inférieur à B et B est inférieur à A) indique une corruption des données d'entrée ou la présence de deux éléments équivalents avec des noms différents.
En l'absence de cycles, la fusion sous la relation moins que doit être simple: retirez de manière répétée les nœuds qui ne peuvent pas être contactés par aucun autre nœud du graphique et les ajoutent à votre liste de sortie. .
Vos listes d'entrée définissent un ordre partiel de vos articles. Selon Une réponse à MATH.SE , ce que vous voulez est un tri topologique . Les algorithmes sont décrits sur Wikipedia.
Vous avez raison ... Vérifié avec Tsort. Rosettacode.org/wiki/topological_sort#Object_pascal
Sortir. Il y a même un programme Linux / Unix Tsort pour cela. Qui savait?
Pouvez-vous utiliser une table de hachage? Voici un algorithme de fusion de deux listes comme ça. Les éléments A [I] où N [I]> 0 Éléments de correspondance de B, les autres seront placés dans une commande valide. Il pourrait y avoir un bug là-bas, mais c'est l'idée générale. pour la fusion de trois tableaux, vous pouvez fusionner les deux premiers, puis fusionner le troisième dans le tableau fusionné.
Sur Modifier, cette dernière phrase est fausse, comme indiqué par @robkennedy. Vous pouvez probablement changer l'algorithme pour gérer trois listes, mais ce n'est pas aussi simple, et vous voudrez peut-être aller avec Topological Trict.
Supposons que les entrées soient {A}, {B}, et {B, A}. Si vous le faites comme indiqué dans votre dernier paragraphe et fusionner les deux premières listes à créer une liste temporaire que vous fusionnez ensuite avec le troisième, vous pourriez obtenir {A, B}, qui contredit la troisième entrée. Vous ne pouvez pas simplement appliquer l'algorithme progressivement ou vous risquez de générer de fausses contraintes; Vous devez traiter toutes les entrées à la fois.
Vous avez donc
E -> T | | A -> Z | ^ R -> W
Nice question. Bien que Trier topologique peut être la méthode la plus recommandée, vous auriez à analyser la saisie d'abord pour créer la liste des dépendances. J'ai pensé à une approche plus dirigée, basée sur la recherche des éléments qui se produisent dans plusieurs listes pour la définition de la commande.
Je suis incapable de prédire quoi que ce soit de la complexité temporelle, mais que vous ne vous souciez pas de la performance et surtout en considérant le Nombre total d'éléments étant 500 au maximum, je pense que cet algorithme devrait fonctionner bien.
Je n'ai pas encore lu et compris votre code, mais cela a fonctionné avec les données de test que j'ai jetées jusqu'à présent.
J'ai accouché mon cerveau et j'ai essayé de me souvenir de ma théorie graphique à UNI pour un algorithme qui pourrait aider. En rien jusqu'à présent jusqu'à présent.
Pas. Sûr. Mettez tous les éléments dans une liste et trier les connaissances extraites de / en fonction de l'ordre de tri de List1, List2, List3, ... une liste après l'autre. Si l'ordre de tri est cohérent sur toutes les 5 listes, cela n'a pas d'importance dans tous les autres cas, vous rencontrerez une erreur. L'ordre d'un élément de la liste d'origine1 par exemple n'est que la position relative au successeur.
J'ai également envisagé cela aussi, @Michael, mais la plupart des algorithmes de tri supposent une commande totale des éléments - ils ne font pas bien lorsque la comparaison de deux éléments peut générer des résultats incohérents. Compte tenu de deux éléments qui n'ont pas défini par une ordonnance relative, comment décidez-vous qui vient en premier de manière cohérente avec les autres données?
Pas besoin du comparateur car la connaissance de l'ordre de tri dans la liste1 est déjà incluse dans la liste de destination.
Ajouter) Pas besoin de comparer car la connaissance de l'ordre de tri dans la liste1 est déjà incluse dans la liste de destination. @Rob Kennedy fait-il importe. Mon idée était de "trier" en fonction de la liste une, puis de la liste 2, puis de la liste 3, ... Il n'y a aucun moyen de dire une position absolue. Vous savez seulement de la liste1 que la position de cet élément est avant son prochain et de la liste2, vous le savez plus spécifiquement, .... Puisqu'il n'y a pas d'ordre naturel, que ferez-vous. Je devrai repenser cela pendant un moment.
Pourquoi ne consistait pas simplement que les listes soient considérées si elles sont toutes triées?
Comment combinez-vous les listes "A B C F" et "A B C H"?