LISP equivalence classes

Question

I need to write a program for equivalence classes and get these outputs ...

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

Basically, a collection is a list in which order does not matter, but items are not displayed more than once. The function must receive a list of pairs (elements which are connected in accordance with an equivalence ratio) and return a set of equivalence classes without iteration or assignment operators (e.g. do, set!etc).

However, specify utilities such as set-intersection, set-unionand a function that excludes duplicates in the list and built-in functions union, intersectionand remove-duplicates.

Thanks a lot!

By the way, this is not a matter of homework. My friend needs this piece of code to solve funny questions.

Answer 1

This sounds like a typical homework question.

It's not that hard though.

A simple recursive function on an input list will be executed. The ingredients of the function are already mentioned in the task description: simple dialing operations.

If this is homework, then it is applicable: a typical strategy for homework is that YOU must first demonstrate your attempt at a solution. This should be, at least in the main, the correct formulation of the algorithm or almost working code. Then Lispers can help you with the finishing touches ...

Well, time passes and there is no solution.

So here Common Lisp is used:

We need three functions.

. - . - . : , , , . , .

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

. , EQUIV-ADD.

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

EQUIV-AUX . , .

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

:

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