リスト間の2つの共通要素

Question

私はこの機能に問題がありますtwo-similar-p。

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

しかし、この機能はTまたはNILで新しいリストを返しますが、私は真または偽を返すためにだけ必要があるため、正しい使用mapcarではありません。

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 

何かアドバイス： My機能は以下のように動作する必要がありますか？

Answer 1

最も簡単な「既製の」解決策はintersectionは、少なくとも二つの要素含まれていることを確認することである。

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

Aわずかに小さい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))))) 

第2のアプローチの利点は、その複雑さがO(len(l1) + len(l2)), であり、mapcarのアプローチがO(len(l1) * len(l2))であることである。

標準では、intersectionとfriendsの複雑さは指定されていませんが、ほとんどの実装ではここでユーザーの注意が払われています（IOW、複雑さは2次ではなく線形になります）。