intersection et union d'une pile

Version imprimable

16/10/2005, 22h35
harris_macken

intersection et union d'une pile

bonjour

existe t il un algorithme pour trouver :
l intersection et l'union de 2 listes L1 et L2

et aussi pour trouver les elements qui sont uniquement dans L1 et uniquement dans L2

merci
17/10/2005, 10h11
FrancisSourd

La liste n'est pas la structure de donnée la plus appropriée pour faire ces opérations. Le plus simple est certainement de passer par des listes triées. En adaptant l'algorithme de fusion de listes triées, on peut faire ces opérations en O(n1+n2) (n1 et n2 sont les longueurs de L1 et L2).

Si le nombre d'objets différents pouvant être inclus dans chaque liste est petit , on peut travailler avec un représentation en tableau de bits.
Exemple: On a au plus 16 objets. Une liste comportant les objets 2 et 9 s'écrit 0100000010000000.
On fait alors l'union et l'intersection en utilisant les opérateurs logiques.
17/10/2005, 13h34
harris_macken

oui suis tout a fait d accord
sauf que j ai la contrainte d utiliser des listes lineaires
17/10/2005, 19h07
Jedai

Tu peux insérer tous tes éléments dans un arbre binaire de recherche puis reconstituer une liste, ainsi tu devrais avoir une moyenne en O(n log n). (En "marquant" les éléments, tu peux te faire ainsi un arbre qui peut servir à extraire l'intersection, l'union ou la différence, mais tout dépend de tes besoins).
Je ne pense pas qu'on puisse faire mieux que du O(n log n) à partir de listes non-triées au départ (ça doit même être assez facile à prouver), mais on peut peut-être améliorer légèrement la méthode proposée ci-dessus. Par contre trier tes listes auparavant peut-être une bonne idée si tu as de gros besoins, et répétitifs. (en fait si tu disposes réellement de listes chaînées, le mieux est sans doute d'adapter l'algorithme du tri fusion)

--
Jedaï
17/10/2005, 19h08
Trap D

Salut
Tes listes sont-elles triées ?
Comment les obtiens-tu ?
Car si elles sont triées, celà va assez vite, car aussi bien pour l'union que pour l'intersection un seul parcours de chaque liste en parallèle est suffisant.
Sinon, il faut parcourir une liste et pour chaque élément de cette liste, parcourir en entier la deuxième liste.
[edit] grillé par jedaï et en plus sa méthode d'arbre de recherche me paraît bien meilleure que la mienne :cry:
[/edit]
17/10/2005, 21h02
harris_macken

nan elle ne sont pas triees
17/10/2005, 21h04
harris_macken

jeday

Citation:

Tu peux insérer tous tes éléments dans un arbre binaire de recherche puis reconstituer une liste, ainsi tu devrais avoir une moyenne en O(n log n).

tu peut expliciter ta methode elle me parait pas mal pour ma sollution
17/10/2005, 21h10
Trap D

Tu peux regarder ici pour avoir une idée des algos, c'est en C, mais assez facilement compréhensible.
18/10/2005, 17h40
harris_macken

Oui j ai vu mais sa m aide pas trop

cependant l idee de Jervais m interesse bien

Citation:

Tu peux insérer tous tes éléments dans un arbre binaire de recherche puis reconstituer une liste, ainsi tu devrais avoir une moyenne en O(n log n). (En "marquant" les éléments, tu peux te faire ainsi un arbre qui peut servir à extraire l'intersection, l'union ou la différence, mais tout dépend de tes besoins).
Je ne pense pas qu'on puisse faire mieux que du O(n log n) à partir de listes non-triées au départ (ça doit même être assez facile à prouver), mais on peut peut-être améliorer

Peut tu me l expliciter

Dans un arbre binaire de recherche a une structure de ce type :

Code:

1
2
3
4
5
6
7
8
// en C
typedef struct noeud
{
  int cle; // la valeur du noeud
  int nb; // le nombre d'occurences ou apparait cette clé 'pour l'intersection des liste
  struct noeud *fg; // le fils gauche 
  struct noeud *fd; // le fils droit
}  noeud;

L'insertion se fait de cette manière, en utilisant la récursivité

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
procedure insertion(valeur, noeud)
  si valeur = noeud.cle alors
     noeud.nb <- noeud.nb + 1
  sinonsi valeur < noeud.cle alors
     si noeud.fg = NULL alors
        noeud.fg <- nouveau_noeud(valeur)
     sinon
          insertion(valeur, noeud.fg)
     finsi
  sinon
      si noeud.fd = NULL alors
         noeud.fd <- nouveau_noeud(valeur)
      sinon
         insertion(valeur, noeud.fd);
      finsi
  finsi
finprocedure

Il y a un cas particulier à traiter, c'est l'initialisation de l'arbre.
Il faut écrire bien sur la fonction nouveau_noeud(valeur)

19/10/2005, 01h28
Jedai

Citation:

Envoyé par harris_macken

Oui j ai vu mais sa m aide pas trop

cependant l idee de Jervais m interesse bien

Peut tu me l expliciter

Jedaï pas Jervais !!
Après réflexion, le plus cohérent me semble un simili-tri fusion SI tu as bien des listes chaînées, est-ce le cas ? (Par ailleurs, quelles sont les tailles de tes listes en moyenne et au pire ?)

--
Jedaï
20/10/2005, 00h50
harris_macken

En fait mes listes sont lineaires

et la taille des listes est elevee et inconnue au prealable
20/10/2005, 09h31
Jedai

Que de précision ! Que signifie "linéaire" dans ton cas : veux-tu dire qu'il s'agit de tableau (donnée stockée contigument en mémoire) ? Par ailleurs tu dois bien avoir un ordre d'idée du "élevé" : de l'ordre du million, du milliard ?

--
Jedaï