列表之間的兩個常見元素

Question

我遇到此功能的問題two-similar-p。

(defun two-similar-p (list1 list2) 
    (mapcar 
    (lambda (e) 
    (mapcar 
     (lambda (e1) 
     (if (equal e e1) t)) 
     list2)) 
    list1)) 

但不正確的使用mapcar，因爲這個函數返回T或NIL一個新的列表，但我只需要返回一個true或false。

ex。

(two-similar-p '(2 1 3) '(1 2 3)) 
==> ((NIL T NIL) (T NIL NIL) (NIL NIL T)) 

我想用遞歸來比較不同的元素，但我不知道該怎麼做。 我的功能需要像這樣工作：

(two-similar-p '(1 2 3) '(1 4 5)) ; ==> nil 

(two-similar-p '(1 2 5) '(1 4 5)) ; ==> t 

(two-similar-p '(1 2 6) '(6 4 2)) ; ==> t 

有什麼建議嗎？

Answer 1

最簡單的「關閉的，現成的」解決方案是檢查intersection含有至少兩種元素：

(defun two-similar-p (l1 l2) 
    (consp (cdr (intersection l1 l2 :test #'equal)))) 

稍微少OTS解決方案是使用hash tables：

(defun two-similar-p (l1 l2) 
    (let ((h1 (make-hash-table :test 'equal)) 
     (common 0)) 
    (dolist (x l1) 
     (setf (gethash x h1) t)) 
    (dolist (x l2) 
     (when (gethash x h1) 
     (incf common)) 
     (when (>= common 2) 
     (return t))))) 

第二種方法的優點是它的複雜性是O(len(l1) + len(l2)), 而mapcar方法將是O(len(l1) * len(l2))。

該標準沒有指定intersection和friends的複雜度，但大多數實現都在這裏好好照顧他們的用戶（IOW，複雜度將是線性的，而不是二次的）。