Classes d'équivalence LISP

Question

Je dois é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))

En fait, un ensemble est une liste dans laquelle l'ordre n'a pas d'importance, mais les éléments ne semblent pas plus d'une fois. La fonction doit accepter une liste de paires (éléments qui sont liés selon une certaine relation d'équivalence), et renvoyer un ensemble de classes d'équivalence, sans l'aide d'instructions d'itération ou de la mission (par exemple do, set!, etc.).

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

Merci beaucoup!

Par ailleurs, ce n'est pas une question de devoirs. Un de mes amis ont besoin de ce morceau de code pour résoudre des questions smilar.

Answer 1

Cela sonne comme une question typique de devoirs.

Il est pas difficile, cependant.

Une fonction récursive simple sur la liste d'entrée fera. Les ingrédients de la fonction sont déjà mentionnées dans la description des tâches:. Opérations de simple jeu

S'il est des devoirs, cela applique: La stratégie typique pour les questions de travail à domicile est que vous devez d'abord montrer votre tentative de solution. Cela devrait être d'au moins une formulation correcte la plupart du temps de l'algorithme ou presque code de travail. Ensuite Lispers peut vous aider avec la touche finale ...

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 paire unique de l'ensemble des couples. Une paire est une liste. L'ensemble de paires est une liste de paires. Pour la paire on calcule deux ensembles: l'ensemble de paires équivalentes et l'ensemble des couples qui ne sont pas équivalentes. Nous combinons les paires équivalentes avec notre paire en entrée 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 à la suite. 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 l'ensemble d'entrée et un résultat vide. En outre, il trie les résultats sous-listes.

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

Exemple de code:

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))