LISP - Ensemble

Common Lisp ne fournit pas de type de données défini. Cependant, il fournit un certain nombre de fonctions qui permettent d'exécuter des opérations sur une liste.

Vous pouvez ajouter, supprimer et rechercher des éléments dans une liste, en fonction de divers critères. Vous pouvez également effectuer diverses opérations d'ensemble telles que: union, intersection et différence d'ensemble.

Implémentation d'ensembles dans LISP

Les ensembles, comme les listes, sont généralement implémentés en termes de contre-cellules. Cependant, pour cette raison même, les opérations sur les ensembles deviennent de moins en moins efficaces à mesure que les ensembles deviennent grands.

le adjoinLa fonction vous permet de constituer un ensemble. Il prend un élément et une liste représentant un ensemble et renvoie une liste représentant l'ensemble contenant l'élément et tous les éléments de l'ensemble d'origine.

le adjoinLa fonction recherche d'abord l'élément dans la liste donnée, si elle est trouvée, elle renvoie la liste d'origine; sinon il crée une nouvelle cellule contre avec soncar comme article et cdr pointant vers la liste d'origine et renvoie cette nouvelle liste.

le adjoin la fonction prend également :key et :testarguments de mots clés. Ces arguments sont utilisés pour vérifier si l'élément est présent dans la liste d'origine.

Étant donné que la fonction adjoin ne modifie pas la liste d'origine, pour effectuer un changement dans la liste elle-même, vous devez soit affecter la valeur retournée par adjoin à la liste d'origine, soit utiliser la macro pushnew pour ajouter un élément à l'ensemble.

Exemple

Créez un nouveau fichier de code source nommé main.lisp et tapez le code suivant dedans.

; creating myset as an empty list
(defparameter *myset* ())
(adjoin 1 *myset*)
(adjoin 2 *myset*)

; adjoin did not change the original set
;so it remains same
(write *myset*)
(terpri)
(setf *myset* (adjoin 1 *myset*))
(setf *myset* (adjoin 2 *myset*))

;now the original set is changed
(write *myset*)
(terpri)

;adding an existing value
(pushnew 2 *myset*)

;no duplicate allowed
(write *myset*)
(terpri)

;pushing a new value
(pushnew 3 *myset*)
(write *myset*)
(terpri)

Lorsque vous exécutez le code, il renvoie le résultat suivant -

NIL
(2 1)
(2 1)
(3 2 1)

Vérification de l'adhésion

Le groupe de fonctions membre vous permet de vérifier si un élément est membre d'un ensemble ou non.

Voici les syntaxes de ces fonctions -

member item list &key :test :test-not :key 
member-if predicate list &key :key 
member-if-not predicate list &key :key

Ces fonctions recherchent dans la liste donnée un élément donné qui satisfait au test. Si aucun élément de ce type n'est trouvé, les fonctions retournentnil. Sinon, la fin de la liste avec l'élément comme premier élément est renvoyée.

La recherche est effectuée uniquement au niveau supérieur.

Ces fonctions peuvent être utilisées comme prédicats.

Exemple

Créez un nouveau fichier de code source nommé main.lisp et tapez le code suivant dedans.

(write (member 'zara '(ayan abdul zara riyan nuha)))
(terpri)
(write (member-if #'evenp '(3 7 2 5/3 'a)))
(terpri)
(write (member-if-not #'numberp '(3 7 2 5/3 'a 'b 'c)))

Lorsque vous exécutez le code, il renvoie le résultat suivant -

(ZARA RIYAN NUHA)
(2 5/3 'A)
('A 'B 'C)

Définir l'union

Le groupe de fonctions union vous permet d'effectuer une union d'ensemble sur deux listes fournies comme arguments à ces fonctions sur la base d'un test.

Voici les syntaxes de ces fonctions -

union list1 list2 &key :test :test-not :key 
nunion list1 list2 &key :test :test-not :key

le unionLa fonction prend deux listes et retourne une nouvelle liste contenant tous les éléments présents dans l'une ou l'autre des listes. En cas de duplication, une seule copie du membre est conservée dans la liste renvoyée.

le nunion La fonction effectue la même opération mais peut détruire les listes d'arguments.

Exemple

Créez un nouveau fichier de code source nommé main.lisp et tapez le code suivant dedans.

(setq set1 (union '(a b c) '(c d e)))
(setq set2 (union '(#(a b) #(5 6 7) #(f h)) 
   '(#(5 6 7) #(a b) #(g h)) :test-not #'mismatch)
)
       
(setq set3 (union '(#(a b) #(5 6 7) #(f h)) 
   '(#(5 6 7) #(a b) #(g h)))
)
(write set1)
(terpri)
(write set2)
(terpri)
(write set3)

Lorsque vous exécutez le code, il renvoie le résultat suivant -

(A B C D E)
(#(F H) #(5 6 7) #(A B) #(G H))
(#(A B) #(5 6 7) #(F H) #(5 6 7) #(A B) #(G H))

Notez s'il vous plaît

La fonction union ne fonctionne pas comme prévu sans :test-not #'mismatcharguments pour une liste de trois vecteurs. En effet, les listes sont constituées de contre-cellules et bien que les valeurs nous semblent identiques, lecdrune partie des cellules ne correspond pas, donc elles ne sont pas exactement identiques à l'interpréteur / compilateur LISP. C'est la raison; il n'est pas conseillé de mettre en œuvre de grands ensembles à l'aide de listes. Cela fonctionne bien pour les petits ensembles.

Définir l'intersection

Le groupe de fonctions d'intersection vous permet d'effectuer l'intersection sur deux listes fournies comme arguments à ces fonctions sur la base d'un test.

Voici les syntaxes de ces fonctions -

intersection list1 list2 &key :test :test-not :key 
nintersection list1 list2 &key :test :test-not :key

Ces fonctions prennent deux listes et renvoient une nouvelle liste contenant tous les éléments présents dans les deux listes d'arguments. Si l'une des listes contient des entrées en double, les entrées redondantes peuvent apparaître ou non dans le résultat.

Exemple

Créez un nouveau fichier de code source nommé main.lisp et tapez le code suivant dedans.

(setq set1 (intersection '(a b c) '(c d e)))
(setq set2 (intersection '(#(a b) #(5 6 7) #(f h)) 
   '(#(5 6 7) #(a b) #(g h)) :test-not #'mismatch)
)
       
(setq set3 (intersection '(#(a b) #(5 6 7) #(f h)) 
   '(#(5 6 7) #(a b) #(g h)))
)
(write set1)
(terpri)
(write set2)
(terpri)
(write set3)

Lorsque vous exécutez le code, il renvoie le résultat suivant -

(C)
(#(A B) #(5 6 7))
NIL

La fonction d'intersection est la version destructive de l'intersection, c'est-à-dire qu'elle peut détruire les listes originales.

Définir la différence

Le groupe de fonctions set-difference vous permet d'exécuter set difference sur deux listes fournies comme arguments à ces fonctions sur la base d'un test.

Voici les syntaxes de ces fonctions -

set-difference list1 list2 &key :test :test-not :key 
nset-difference list1 list2 &key :test :test-not :key

La fonction set-difference renvoie une liste d'éléments de la première liste qui n'apparaissent pas dans la seconde liste.

Exemple

Créez un nouveau fichier de code source nommé main.lisp et tapez le code suivant dedans.

(setq set1 (set-difference '(a b c) '(c d e)))
(setq set2 (set-difference '(#(a b) #(5 6 7) #(f h)) 
   '(#(5 6 7) #(a b) #(g h)) :test-not #'mismatch)
)
(setq set3 (set-difference '(#(a b) #(5 6 7) #(f h)) 
   '(#(5 6 7) #(a b) #(g h)))
)
(write set1)
(terpri)
(write set2)
(terpri)
(write set3)

Lorsque vous exécutez le code, il renvoie le résultat suivant -

(A B)
(#(F H))
(#(A B) #(5 6 7) #(F H))