Classi di equivalenza LISP

Question

ho bisogno di scrivere un programma per le classi di equivalenza e di ottenere questo uscite ...

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

In sostanza, Un set è una lista in cui l'ordine non importa, ma gli elementi non appaiono più di una volta. La funzione dovrebbe accettare una lista di coppie (elementi che sono collegati secondo alcuni relazione di equivalenza), e restituire un insieme di classi di equivalenza senza usare istruzioni di iterazione o assegnazione (ad esempio do, set!, ecc.).

Tuttavia, impostare utility come set-intersection, set-union e una funzione che elimina i duplicati in un elenco e funzioni built-in union, intersection, e remove-duplicates sono ammessi.

Grazie mille!

A proposito, non è una domanda compiti a casa. Un mio amico ha bisogno di questo pezzo di codice per risolvere questioni smilar.

Answer 1

che suona come una domanda tipica compiti a casa.

Non è così difficile, però.

Una semplice funzione ricorsiva oltre l'elenco di ingresso farà. Gli ingredienti della funzione sono già menzionate nella descrizione compito:. Semplice operazione di set

Se è compiti a casa, allora questo vale: La strategia tipica per le domande compiti a casa è che si deve mostrare prima il tentativo di soluzione. Questo dovrebbe essere almeno principalmente una corretta formulazione dell'algoritmo o quasi codice funzionante. Poi Lispers può aiutarvi con gli ultimi ritocchi ...

Bene, il tempo passa e nessuna soluzione.

Così qui è uno che utilizza Common Lisp:

Abbiamo bisogno di tre funzioni.

La prima funzione aggiunge una sola coppia per l'insieme delle coppie. Una coppia è una lista. L'insieme delle coppie è una lista di coppie. Per la coppia si calcola due insiemi: l'insieme delle coppie che sono equivalenti e l'insieme delle coppie che non sono equivalenti. Uniamo le coppie equivalenti nostro in ingresso coppia in un unico insieme.

(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 seconda funzione aggiunge ciascuna coppia di una serie di coppie al risultato. E li aggiunge chiamando EQUIV-ADD.

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

La terza funzione chiama semplicemente EQUIV-AUX con il set di input e un risultato vuoto. Inoltre si ordina le sottoliste risultato.

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

Esempio chiama:

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