等價類LISP

Question

我需要編寫等價類的節目，並獲得此輸出......

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

基本上，一組是其中的順序並不重要的列表，但元素不出現不止一次。 該函數應接受一對對（根據某種等價關係相關的元素）列表，並返回一組等價類而不使用迭代或賦值語句（例如do,set!等）。

然而，一套實用程序，如set-intersection，set-union和其消除在一個列表中的重複和內置函數union，intersection的函數，並且remove-duplicates是允許的。

非常感謝！

順便說一下，這不是一個家庭作業問題。我的一位朋友需要這段代碼來解決類似的問題。

Answer 1

這聽起來像一個典型的作業問題。

雖然這並不困難。

輸入列表上的簡單遞歸函數將會執行。該功能的組成部分已在任務描述中提及：簡單設置操作。

如果是家庭作業，那麼這適用於：家庭作業問題的典型策略是，您必須首先展示您的解決方案嘗試。這應該至少是算法或幾乎可用的代碼的最正確的表達方式。然後Lispers可能會幫助你完成最後的步驟...

那麼，時間流逝，沒有解決方案。

所以這裏是一個使用Common Lisp：

我們需要三個函數。

第一個函數向該組對中添加一對。一對是一個列表。這組對是一對列表。對於我們來說，我們計算兩組數據：一組是相同的對，另一組是不相等的對。我們將與我們在輸入對中相同的對組合成一個集合。

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