等价类 LISP

发布于 2024-08-31 00:10:36 字数 563 浏览 7 评论 0原文

我需要为等价类编写一个程序并获得此输出...

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

基本上,集合是一个列表,其中顺序无关紧要,但元素不会出现多次。 该函数应该接受一个对列表(根据某种等价关系相关的元素),并返回一组等价类,而不使用迭代或赋值语句(例如doset!< /代码>等)。

但是,设置实用程序,例如 set-intersectionset-union 以及消除列表中重复项的函数和内置函数 union,允许交集remove-duplicates

多谢!

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

I need to write a program for equivalence classes and get this outputs...

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

Basically, A set is a list in which the order doesn't matter, but elements don't appear more than once.
The function should accept a list of pairs (elements which are related according to some equivalence relation), and return a set of equivalence classes without using iteration or assignment statements (e.g. do, set!, etc.).

However, set utilities such as set-intersection, set-union and a function which eliminates duplicates in a list and built-in functions union, intersection, and remove-duplicates are allowed.

Thanks a lot!

By the way, It's not a homework question. A friend of mine need this piece of code to solve smilar questions.

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(1

糖粟与秋泊 2024-09-07 00:10:37

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

不过,这并没有那么困难。

对输入列表进行简单的递归函数就可以了。该函数的组成部分已在任务描述中提到:简单的集合运算。

如果是家庭作业,则适用:家庭作业问题的典型策略是您必须首先展示您的解决方案尝试。这至少应该是算法的基本正确表述或几乎可以工作的代码。然后 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))

That sounds like a typical homework question.

It's not that difficult, though.

A simple recursive function over the input list will do. The ingredients of the function are already mentioned in the task description: simple set operations.

If it is homework, then this applies: The typical strategy for homework questions is that YOU have to show first your solution attempt. That should be at least a mostly correct formulation of the algorithm or almost working code. Then Lispers may help you with the finishing touches...

Well, time passes and no solution.

So here is one using Common Lisp:

We need three functions.

The first function adds a single pair to the set of pairs. A pair is a list. The set of pairs is a list of pairs. For the pair we compute two sets: the set of pairs that are equivalent and the set of pairs that are not equivalent. We combine the pairs that are equivalent with our in input pair into a single set.

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

The second function adds each pair of a set of pairs to the result. It adds them by calling EQUIV-ADD.

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

The third function just calls EQUIV-AUX with the input set and an empty result. Additionally it sorts the result sublists.

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

Example calls:

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))
~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文