等价类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))

基本上，set是一个列表，其中的顺序并不重要，但元素不会出现多次。该函数应该接受一组对(根据某种等价关系相关的元素)，并返回一组等价类，而不使用迭代或赋值语句(例如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))