CODEWITHSUNDEEP
lispcommon-lisp
Gabriele Bisogno
Gabriele Bisogno

Reputation: 5

Two common elements between lists

I have a problem with this function two-similar-p.

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

But is not correct use mapcar because this function returns a new list with T or NIL, but I need only to return a true or false.

ex.

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

I was thinking to use recursion to compare the various elements, but I have no idea how to do that. My function needs to work like:

(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

Any advice?

Upvotes: 0

Views: 607

Answers (1)

sds
sds

Reputation: 60064

The easiest "off-the-shelf" solution is to check that the intersection contains at least two elements:

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

A slightly less OTS solution is to use 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)))))

The advantage of the second approach is that its complexity is O(len(l1) + len(l2)), while the mapcar approach will be O(len(l1) * len(l2)).

The standard does not specify the complexity of intersection and friends, but most implementations take good care of their users here (IOW, the complexity will be linear, not quadratic).

Upvotes: 1

Related Questions