¨Aquivalenzklassen LISP

Question

Ich brauche ein Programm für die Äquivalenzklassen zu schreiben und erhalten diese Ausgänge ...

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

Im Grunde ist ein Satz eine Liste, in der die Reihenfolge spielt keine Rolle, aber Elemente mehr nicht als einmal. Die Funktion sollte eine Liste von Paaren (Elemente, die nach einiger Äquivalenzbeziehung verbunden sind anzunehmen, und einen Satz von Äquivalenzklassen zurückzukehren, ohne Iteration oder Zuweisungsanweisungen (z.B. do, set!, etc.).

Allerdings Satz Dienstprogramme wie set-intersection, set-union und eine Funktion, die eliminiert Duplikate in einer Liste und integrierte Funktionen union, intersection und remove-duplicates sind erlaubt.

Vielen Dank!

übrigens, es ist keine Hausaufgabe Frage. Ein Freund von mir brauchen Sie dieses Stück Code smilar Fragen zu lösen.

Answer 1

Das klingt wie eine typische Hausaufgaben Frage.

Es ist nicht so schwierig, aber.

Eine einfache rekursive Funktion über die Eingabeliste tun. Die Bestandteile der Funktion sind bereits in der Aufgabenbeschreibung erwähnt. Einfachen Set-Operationen

Wenn es Hausaufgaben, dann gilt dies: Die typische Strategie für die Hausaufgaben Fragen ist, dass Sie zunächst Ihre Lösung Versuch zeigen. Das sollte eine meist korrekte Formulierung des Algorithmus oder fast funktionierenden Code zumindest sein. Dann Lispers können Sie mit den letzten Schliff helfen ...

Nun, die Zeit vergeht und keine Lösung.

Hier ist also eine Common Lisp mit:

Wir brauchen drei Funktionen.

Die erste Funktion fügt ein einzelnes Paar an den Satz von Paaren. Ein Paar ist eine Liste. Der Satz von Paaren ist eine Liste von Paaren. Für das Paar berechnen wir zwei Gruppen: die Menge der Paare, die äquivalent und der Satz von Paaren sind, die nicht äquivalent sind. Wir verbinden die Paare, die in einen einzigen Satz mit unserem in Eingangspaar äquivalent sind.

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

Die zweite Funktion fügt jedes Paar von einem Satz von Paaren zum Ergebnis. Sie fügt hinzu, sie durch EQUIV-ADD aufrufen.

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

Die dritte Funktion nennt nur EQUIV-AUX mit dem Eingangssatz und ein leeres Ergebnis. Zusätzlich sortiert es das Ergebnis Sublisten.

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

Beispiel aufruft:

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