比较集合的函数; 有助于提高效率

Question

我正在尝试编写一个比较两个列表的函数,看它们是否代表相同的集合.这是'(a b c d d)与'(d c b a d)代表同一组.元素可以是任何顺序.

这就是我所拥有的,它有效:

(defun samesetp (list1 list2)
  (cond
    ((null list1) (null list2))
    ((eq list2 (remove (car list1) list2 :count 1)) nil)
    (t (samesetP (cdr list1) (remove (car list1) list2 :count 1))))))

我不喜欢这个的原因(remove (car list1) list2 :count 1))是计算两次 - 一次测试remove操作是否真正删除了任何东西,一次递归测试列表的其余部分没有.

任何人都可以提出一种方法来改善这一点,而不使用不同的算法

Answer 1

(defun samesetp (list1 list2)
    (cond
        ((null list1) (null list2))
        ((eq list2 (remove (car list1) list2 :count 1)) nil)
        (t (samesetP (cdr list1) (remove (car list1) list2 :count 1))))
    )
)

首先让我们正确格式化:

(defun samesetp (list1 list2)
  (cond ((null list1) (null list2))
        ((eq list2 (remove (car list1) list2 :count 1)) nil)
        (t (samesetP (cdr list1) (remove (car list1) list2 :count 1)))))

如果您使用表单两次并且想要更改它,那么您需要存储一个值.LET是它的构造.如果它不适合一个COND,那么你需要第二个.

(defun samesetp (list1 list2)
  (cond ((null list1) (null list2))
        (t (let ((list3 (remove (car list1) list2 :count 1)))
             (cond ((eq list2 list3) nil)
                   (t (samesetP (cdr list1) list3)))))))

现在,EQ不能用于比较列表.使用EQUAL.

(defun samesetp (list1 list2)
  (cond ((null list1) (null list2))
        (t (let ((list3 (remove (car list1) list2 :count 1)))
             (cond ((equal list2 list3) nil)
                   (t (samesetP (cdr list1) list3)))))))

COND在这里过度,使用IF:

(defun samesetp (list1 list2)
  (if (null list1)
      (null list2)
    (let ((list3 (remove (car list1) list2 :count 1)))
      (if (equal list2 list3)
          nil
        (samesetP (cdr list1) list3)))))

现在,您只需要让功能完成作业中的要求.但无论如何,这是你的功课.