用於比較集合的函數;有助於提高效率

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)