等价类 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的实用程序。

非常感谢！

顺便说一下，这不是一个作业问题。我的一个朋友需要这段代码来解决类似的问题。

- bubdada

---

如果这是一份作业，你能把它标记为作业吗？这样做会得到更合适的答案。 - Nathan Shively-Sanders

听起来像是作业... - Michiel Borkent

那么是谁定义了这些限制（如无迭代等），为什么？ - Rainer Joswig

因为这是一本书中的问题... - bubdada

Answer 1

这听起来像是一个典型的作业问题。但并不难。只需要对输入列表进行简单的递归函数即可。该任务描述中已经提到了函数的要素：简单的集合操作。

如果这是一道作业题，那么你需要先展示你自己的解决方案。至少应该准确地表述算法或几乎能工作的代码。然后Lisp程序员可以帮助你完成最后的调整...

时间过去了，还没有解决方案。因此，这里提供了一个使用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))

- Rainer Joswig