Classes d'équivalence Lisp

Question

J'ai besoin d'écrire un programme pour les classes d'équivalence et d'obtenir cette sortie ...

(equiv '((a b) (a c) (d e) (e f) (c g) (g h))) 
=> ((a b c g h) (d e f)) 

(equiv '((a b) (c d) (e f) (f g) (a e))) 
=> ((a b e f g) (c d)) 

Fondamentalement, un ensemble est une liste dans laquelle l'ordre n'a pas d'importance, mais les éléments ne le font pas apparaître plus d'une fois. La fonction doit accepter une liste de paires (éléments liés selon une relation d'équivalence) et renvoyer un ensemble de classes d'équivalence sans utiliser d'instructions d'itération ou d'affectation (par exemple do, set!, etc.).

Cependant, les services publics tels que set-intersection ensemble, set-union et une fonction qui élimine les doublons dans une liste et fonctions intégrées union, intersection et remove-duplicates sont autorisés.

Merci beaucoup! En passant, ce n'est pas une question de devoirs. Un de mes amis a besoin de ce morceau de code pour résoudre des questions smilar.

Answer 1

Cela ressemble à une question de devoirs typique.

Ce n'est pas si difficile, cependant.

Une fonction récursive simple sur la liste d'entrée fera l'affaire. Les ingrédients de la fonction sont déjà mentionnés dans la description de la tâche: opérations simples. S'il s'agit de devoirs, alors ceci s'applique: La stratégie typique pour les devoirs est que VOUS devez d'abord montrer votre tentative de solution. Cela devrait être au moins une formulation la plus correcte de l'algorithme ou presque du code de travail. Alors Lispers peut vous aider avec les touches de finition ...

Eh bien, le temps passe et pas de solution.

Voici donc une aide de Common Lisp:

Nous avons besoin de trois fonctions.

La première fonction ajoute une seule paire à l'ensemble des paires. Une paire est une liste. L'ensemble des paires est une liste de paires. Pour la paire, nous calculons deux ensembles: l'ensemble des paires qui sont équivalentes et l'ensemble des paires qui ne sont pas équivalentes. Nous combinons les paires qui sont équivalentes avec notre paire d'entrées en un seul ensemble.

(defun equiv-add (e l) 
    (let ((l- (remove-if  (lambda (i) (intersection e i)) l)) 
     (l+ (remove-if-not (lambda (i) (intersection e i)) l))) 
    (cons (remove-duplicates (reduce #'union (cons e l+))) 
      l-))) 

La deuxième fonction ajoute chaque paire d'un ensemble de paires au résultat. Il les ajoute en appelant EQUIV-ADD.

(defun equiv-aux (list result) 
    (if (null list) 
     result 
    (equiv-aux (rest list) 
       (equiv-add (first list) 
          result)))) 

La troisième fonction appelle simplement EQUIV-AUX avec le jeu d'entrée et un résultat vide. De plus, il trie les sous-listes de résultats.

(defun equiv (list) 
    (mapcar (lambda (el) 
      (sort el #'string-lessp)) 
      (equiv-aux list '()))) 

Exemple appelle:

CL-USER 34 > (equiv '((a b) (c d) (e f) (f g) (a e))) 
((A B E F G) (C D)) 

CL-USER 35 > (equiv '((a b) (a c) (d e) (e f) (c g) (g h))) 
((A B C G H) (D E F))