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

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，那么你需要第二个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))))) 

现在，你只需要进行功能做什么被要求在作业。但无论如何，这是你的家庭作业。

Answer 2

我猜你是不是允许使用内置函数来解决这个问题，只是要注意有一个：

(set-difference list1 list2)