clases de equivalencia Lisp

Question

Tengo que escribir un programa de clases de equivalencia y obtener este salidas ...

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

Básicamente, Un conjunto es una lista en la que el orden no es importante, pero no lo hacen los elementos aparecer más de una vez La función debe aceptar una lista de pares (elementos que están relacionados de acuerdo con alguna relación de equivalencia) y devolver un conjunto de clases de equivalencia sin usar declaraciones de iteración o asignación (por ejemplo, do, set!, etc.).

Sin embargo, las utilidades de ajuste están permitidos como set-intersection, set-union y una función que elimina duplicados en una lista y funciones integradas en union, intersection, y remove-duplicates.

¡Muchas gracias!

Por cierto, no es una pregunta para la tarea. Un amigo mío necesita esta pieza de código para resolver preguntas similares.

Answer 1

Eso suena como una típica pregunta de tarea.

No es tan difícil, sin embargo.

Una función recursiva simple sobre la lista de entrada funcionará. Los ingredientes de la función ya se mencionan en la descripción de la tarea: operaciones de configuración simple.

Si se trata de tareas, esto aplica: La estrategia típica para las tareas es que USTED tiene que mostrar primero su intento de solución. Esa debería ser, al menos, una formulación correcta del algoritmo o código casi operativo. Entonces Lispers puede ayudarle con los toques finales ...

Bueno, el tiempo pasa y no hay solución.

Así que aquí es uno que utiliza Common Lisp:

necesitamos tres funciones.

La primera función agrega un solo par al conjunto de pares. Un par es una lista. El conjunto de pares es una lista de pares. Para el par calculamos dos conjuntos: el conjunto de pares que son equivalentes y el conjunto de pares que no son equivalentes. Combinamos los pares que son equivalentes con nuestro par de entrada en un solo conjunto.

(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 segunda función agrega cada par de un par de pares al resultado. Los agrega llamando EQUIV-ADD.

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

La tercera función simplemente llama a EQUIV-AUX con el conjunto de entrada y un resultado vacío. Además, ordena las sublistas de resultados.

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

Ejemplo llama:

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