4

我有一个 lisp 作业，我很难处理它。

我必须编写一个执行联合操作的函数。该函数接受 2 个输入，以原子或列表的形式，并联合每个元素，保留顺序并去除所有级别的括号。

函数的输出：

(my-union 'a 'b)                         ;; (a b)
(my-union 'a '(b))                       ;; (a b)
(my-union '(a b) '(b c))                 ;; (a b c)
(my-union '(((a))) '(b(c((d e))a)))      ;; (a b c d e)

我对 lisp 很陌生。这是我到目前为止所写的内容，它仅适用于第三个示例：

(defun new-union (a b)
 (if (not b)
      a
      (if (member (car b) a)
        (new-union a (cdr b))
        (new-union (append a (list (car b))) (cdr b)))))

任何帮助，将不胜感激！

4

3 回答 3

5

由于这是你的第一个作业，而且你是 Lisp 新手，这里有一个非常简单的自上而下的方法，不用担心性能，并充分利用 CL 提供的工具：

在 Common Lisp 中，已经有一个删除重复项的功能：remove-duplicates. 将它与:from-end关键字参数一起使用将“保留顺序”。现在，假设您有一个函数flatten，它可以展平任意嵌套的列表。那么您的问题的解决方案是：

(defun new-union (list1 list2)
  (remove-duplicates (flatten (list list1 list2)) :from-end t))

这就是我在没有进一步限制的情况下解决问题的方法，并且没有真正的理由担心性能。尽可能多地使用现有的工具箱，除非必要，否则不要重新发明轮子。

如果你这样处理问题，归结为编写flatten函数，我将把它作为练习留给你。这不是太难，一个简单的选择是编写一个递归函数，解决这样的问题：

如果要展平的列表的第一个元素本身就是一个列表，则将展平的第一个元素附加到展平的其余部分。如果第一个元素不是列表，只需将其添加到列表的展平其余部分。如果输入根本不是列表，只需返回它。

这对你来说应该是一个很好的练习，只需几行代码就可以完成。

（如果你想非常正确，请使用辅助函数来完成这项工作并检查包装函数是否参数真的是一个列表。否则，flatten也适用于原子，这对你来说可能是也可能不是问题.)

现在，假设你已经写了flatten：

> (defun new-union (list1 list2)
    (remove-duplicates (flatten (list list1 list2)) :from-end t))
NEW-UNION
> (new-union 'a 'b)
(A B)
> (new-union 'a '(b))
(A B)
> (new-union '(a b) '(b c))
(A B C)
> (new-union '(((a))) '(b (c ((d e)) a)))
(A B C D E)
于 2012-09-30T13:10:32.393 回答
3

解决此问题的一种方法是将您的关注点分开。一是扁平化；另一个是重复删除；还有一个是建立结果。

从作为结果的空列表开始，继续将第一个列表的元素添加到其中，跳过结果中已经存在的元素。

然后对第二个列表的元素执行相同的操作，将它们添加到相同的结果列表中。

(defun my-union (a b &aux (res (list 1)) (p res))
  (nadd-elts p a)
  (nadd-elts p b)
  (cdr res))

nadd-eltsp将添加到列表的末尾，使用 eg破坏性地更新其最后一个单元格（由 指向） rplacd。一个例子是here。

要添加元素，nadd-elts将模拟展平过程，并p在检查res重复项后添加每个叶元素。

以功能风格工作，没有破坏性更新，一般方法保持不变：从空结果列表开始，将第一个列表添加到其中 - 没有重复 - 然后是第二个。

(defun my-union (a b &aux res)
  (setq res (add-into res a))
  (setq res (add-into res b))
  res)

现在我们要实现这个add-into功能了。

(defun add-into (res a &aux r1 r2)
  (cond
     ((atom a) .... )
     (T (setq r1 (add-into res (car a)))
        (setq r2 (............ (cdr a)))
        r2)))

上面的内容可以在没有辅助变量和原语的情况下重写set。试着找出如何......好吧，这就是我的意思：

(defun my-union (a b) (add-into NIL (cons a b)))

(defun add-into (res a)
  (cond
     ((atom a) .... )
     (T (add-into (add-into res (car a)) 
                  (cdr a)))))
于 2012-09-30T07:57:22.887 回答
2

除非您不允许使用哈希表（出于某种原因，我以前曾遇到过此要求），否则您可以提出一个排序函数，以帮助您以您没有的方式构建结果集一遍又一遍地重复搜索。

此外，由于允许嵌套列表，因此您的问题缩小到仅删除树中的重复项（因为您可以在开始处理它们之前简单地附加任意数量的列表。

现在，我将尝试展示一些示例来说明如何做到这一点：

;; Large difference between best and worst case.
;; Lists containing all the same items will be processed
;; in square time
(defun union-naive (list &rest lists)
  (when lists (setf list (append list lists)))
  (let (result)
    (labels ((%union-naive (tree)
               (if (consp tree)
                   (progn
                     (%union-naive (car tree))
                     (when (cdr tree) (%union-naive (cdr tree))))
                   (unless (member tree result)
                     (setq result (cons tree result))))))
      (%union-naive list) result)))

;; Perhaps the best solution, it is practically linear time
(defun union-hash (list &rest lists)
  (when lists (setf list (append list lists)))
  (let ((hash (make-hash-table)) result)
    (labels ((%union-hash (tree)
               (if (consp tree)
                   (progn
                     (%union-hash (car tree))
                     (when (cdr tree) (%union-hash (cdr tree))))
                   (setf (gethash tree hash) t))))
      (%union-hash list))
    (maphash
     #'(lambda (a b)
         (declare (ignore b))
         (push a result)) hash)
    result))

;; This will do the job in more time, then the
;; solution with the hash-map, but it requires
;; significantly less memory. Memory is, in fact
;; a more precious resource some times, but you
;; have to decide what algo to use based on the
;; data size
(defun union-flatten (list &rest lists)
  (when lists (setf list (append list lists)))
  (labels ((%flatten (tree)
             (if (consp tree)
                 (if (cdr tree)
                     (nconc (%flatten (car tree))
                            (%flatten (cdr tree)))
                     (%flatten (car tree)))
                 (list tree))))
    ;; the code below is trying to do something
    ;; that you could've done using 
    ;; (remove-duplicates (%flatten list))
    ;; however sorting and then removing duplicates
    ;; may prove to be more efficient
    (reduce
     #'(lambda (a b)
         (cond
           ((atom a) (list a))
           ((eql (car a) b) b)
           (t (cons b a))))
     (sort (%flatten list)
           #'(lambda (a b)
               (string< (symbol-name a)
                        (symbol-name b)))))))



(union-naive '(((a))) '(b(c((d e))a)))
(union-hash '(((a))) '(b(c((d e))a)))
(union-flatten '(((a))) '(b(c((d e))a)))

请注意，我用来对元素排序的函数不是通用的，但您可能能够为任何类型的数据想出一个替代函数。一般来说，任何快速散列函数都可以，为了简单起见，我使用了这个函数。

于 2012-09-30T12:25:35.760 回答