等效类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!, ， ETC。）。

但是，设置公用事业，例如 set-intersection, set-union 以及消除列表和内置功能中重复的功能 union, intersection, ， 和 remove-duplicates 被允许。

非常感谢！

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

Answer 1

这听起来像是一个典型的作业问题。

不过，这并不困难。

输入列表上的简单递归功能将完成。该功能的成分在任务说明中已经提到：简单的设置操作。

如果是作业，那么这将适用：家庭作业问题的典型策略是您必须首先展示解决方案尝试。这至少应该是算法或几乎工作代码的最多正确的公式。然后，Lispers可能会帮助您完成修饰...

好吧，时间过去了，没有解决方案。

因此，这是使用常见的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))