Combinaison de plusieurs listes Triés

Question

Considérons L1, L2, L3 sous forme de listes contenant n1, entiers et n3 dans n2 ordre de tri respectivement.

tâche est de construire une liste L triée de telle sorte que,

 
L[0] = L1[0] + L2[0] + L3[0] 
L[i] = L1[i1] + L2[i2] + L3[i3] 
L[n1 * n2 * n3] = L1[n1] + L2[n2] + L3[n3] 

Mais n1, n2, n3 sont très grandes et, par conséquent L ne peut pas être construit en une seule fois, puis triés.

Par conséquent, la liste doit être construite par étapes et telle que nous puissions afficher k entiers supérieurs et enregistrer l'état de calcul pour reprendre en calculant [k + 1] e entier supérieur.

Qu'est-ce que toutes les structures de données et algorithmes peuvent être utilisés pour atteindre l'objectif?

Answer 1

tu ne peux pas utiliser un merge sort modifié, puisque vous avez déjà trois listes triées? (Par "modifié" je veux dire quelque chose qui tire parti du fait que vous savez que chaque liste d'entrée est déjà triée.)

En supposant que vous ne pouvez pas utiliser un tri de fusion directement, car vous ne voulez pas calculer, en mémoire , toute la liste triée nouvellement fusionnée, que diriez-vous de ceci: Utilisez un tri de fusion modifié où vous calculez le premier groupe d'entrées fusionnées et les affichez, en maintenant les pointeurs utilisés dans le tri de la fusion. Vous persistez juste où vous êtes dans chaque liste, un pointeur vers l'emplacement actuel dans chaque liste, et reprenez là où vous vous étiez arrêté pour chaque morceau.

Answer 2

Ok, je vais peut-être flambé par cette réponse. Mais puisque vous avez seulement besoin de l'algorithme, la meilleure solution serait de tranverser chaque liste en même temps en construisant la liste des résultats avec le meilleur élément (dans ce cas, le plus bas, ou celui que vous aimez dans une égalité). Avec cette méthode, vous avez 4 positions, une pour chaque liste que vous trasversing et le dernier point pourrait pointer vers la position dans la liste des résultats que vous avez besoin d'insérer (ou la dernière position d'insertion). Avec cela, la seule structure dont vous avez besoin est une liste.

Je vois un problème avec sorte de fusion dans ce cas. Les données que vous montrez pourraient ne pas être les données exactes (puisque vous devez trier la partie suivante, et cela pourrait être fusionné avec le courant).

Answer 3

OK, d'abord un exemple en deux dimensions:

 
    1 2 3 

1 2 3 4 
5 6 7 8 
7 8 9 10 

Vous commencez dans le coin en haut à gauche, évidemment, et mettre la valeur dans la liste des résultats. Ensuite, vous devez ajouter tous les candidats qui sont accessibles (en incrémentant exactement un index) à partir d'une sorte de collection triée, ici, c'est-à-dire les cellules avec les valeurs 3 et 6. Ensuite, vous prenez le membre le plus bas de cette collection , place sa valeur dans la liste des résultats, y ajoute tous les candidats qui ne sont pas encore dans la collection, et ainsi de suite.

Vous aurez besoin:

• une structure de données contenant un candidat, avec tous les indices et la valeur de résultat (je représente que ci-après « ((i1 i2) value) »).
• une structure de données pour une collection de candidats, triée par valeur. Un tas semble idéal pour cela.

Vous devrez vous assurer que tous les candidats sont uniques par leurs indices lorsque vous les mettez dans la collection. Les valeurs ne sont pas nécessairement uniques, mais le tas doit être trié par eux.Comme un ensemble donné d'indices produit toujours la même valeur, vous devrez vérifier l'unicité des indices uniquement lorsque vous rencontrez cette valeur lors de l'insertion dans le tas. Il peut s'agir d'une optimisation pour que les nœuds du tas ne soient pas des candidats uniques mais une liste de candidats ayant la même valeur. Pour cela, avec l'exemple ci-dessus: D'abord, la liste des résultats est (2). Les candidats sont ((1 2) 3) et ((2 1) 6). Prenez le candidat avec la valeur la plus basse, mettez la valeur dans la liste des résultats -> (2 3), trouvez toutes les coordonnées des nouveaux candidats -> (2 2) et (1 3), calculez leurs valeurs -> ((2 2) 7) et ((1 3) 4), les mettre dans le tas des candidats (représentation sérialisée ici) -> ((1 3) 4) ((2 1) 6) ((2 2) 7), mousse, rincez, répétez.

Sous forme de tableau:

 
result-list   candidates 
(2)     ((1 2) 3) ((2 1) 6) 
(2 3)    ((1 3) 4) ((2 1) 6) ((2 2) 7) 
(2 3 4)    ((2 1) 6) ((2 2) 7) ((2 3) 8) 
(2 3 4 6)   ((2 2) 7) ((3 1) 8) ((2 3) 8) 
(2 3 4 6 7)   ((3 1) 8) ((2 3) 8) ((3 2) 9) 
(2 3 4 6 7 8)  ((2 3) 8) ((3 2) 9) 
(2 3 4 6 7 8 8)  ((3 2) 9) ((3 3) 10) 
(2 3 4 6 7 8 8 9) ((3 3) 10) 
(2 3 4 6 7 8 8 9 10) 

je ne vois pas une meilleure façon pour le moment. Le tas semble avoir besoin d'un nombre de nœuds de l'ordre de la somme de n1, n2 et n3.