列表之间的两个常见元素

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，复杂度将是线性的，而不是二次的）。