Las 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 importa, pero los elementos no aparecen más de una vez. La función debe aceptar una lista de pares (elementos que están relacionados de acuerdo con algún relación de equivalencia), y devolver un conjunto de clases de equivalencia sin usar declaraciones de iteración o cesión (por ejemplo do, set!, etc.).

Sin embargo, las utilidades de ajuste tales como set-intersection, set-union y una función que elimina duplicados en una lista y funciones incorporadas se permite union, intersection, y remove-duplicates.

Muchas gracias!

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

Answer 1

Eso suena como una pregunta típica tarea.

No es tan difícil, sin embargo.

Una función recursiva simple a través de la lista de entrada va a hacer. Los ingredientes de la función ya se mencionan en la descripción de la tarea:. Operaciones de conjuntos sencilla

Si se trata de la tarea, a continuación, esto se aplica: La estrategia típica para preguntas de la tarea es que usted tiene que demostrar primero su intento de solución. Eso debería ser al menos la mayoría formulación correcta del algoritmo o código de trabajo casi. Entonces Lispers que puede ayudar 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 añade 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 de entrada de par 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 añade cada par de un conjunto de pares al resultado. Se les añade llamando EQUIV-TDA.

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

La tercera función sólo llama EQUIV-AUX con el conjunto de entrada y un resultado vacío. Además ordena los sub-listas 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))