CODEWITHSUNDEEP
lispcommon-lispset-intersection
user9574667
user9574667

Reputation:

Lisp/Intersection of Lists

Hello i am trying to create a function in common-lisp that takes two lists, and output their intersections, assuming there is no repetition in each list without using intersection function. It seems that it is not working. Can anyone help?

(defun isect (lst_1 lst_2)
    (setq newlist nil)
    (dolist (x lst_1 newlist)
        (dolist (y lst_2) 
            (if (equal x y) (setf newlist (append newlist x)))
        )
    )
)

Upvotes: 2

Views: 2554

Answers (4)

Gwang-Jin Kim
Gwang-Jin Kim

Reputation: 9865

;; the key function for simple lists
(defun id (x) x)

;; the intersect function for two lists
;; with sorting included:
;; you need an equality-test:
;;   default is #'eql (for simple numbers or symbols this is sufficient)
;;   - for numbers only    #'=
;;   - for characters only #'char=
;;   - for strings only    #'string=
;;   - for lists           #'equal
;;   - for nearly everything #'equalp (case insensitive for char/strings!)
;; then you need also a sorting tester:
;; - increasing number:  #'<
;; - decreasing number:  #'>
;; - increasing char:    #'char<
;; - decreasing char:    #'char>
;; - increasing strings: #'string<
;; - decreasing strings: #'string>
;; - other cases I haven't think of - does somebody have an idea?
;;   (one could sort by length of element etc.)
;;   so sort-test should be a diadic function (function taking 2 arguments to compare)
;; then you also need an accessor function
;;   so, how withing each element the to-be-sorted element should be accessed
;;   for this, I prepared the `id` - identity - function because this is the
;;   sort-key when simple comparison of the elements of the two lists
;;   should be compared - and this function is also used for testing
;;   for equality in the inner `.isect` function.
(defun isect (lst-1 lst-2 &key (equality-test #'eql) (sort-test #'<) (sort-key #'id))
  (let ((lst-1-sorted (stable-sort lst-1 sort-test :key sort-key))
        (lst-2-sorted (stable-sort lst-2 sort-test :key sort-key)))
    (labels ((.isect (l1 l2 acc)
              (cond ((or (null l1) (null l2)) (nreverse acc))
                    (t (let ((l1-element (funcall sort-key (car l1)))
                             (l2-element (funcall sort-key (car l2))))
                         (cond ((funcall sort-test l1-element l2-element)
                                (.isect (cdr l1) l2 acc))
                               ((funcall equality-test l1-element l2-element)
                                (.isect (cdr l1) (cdr l2) (cons (car l1) acc)))
                               (t (.isect l1 (cdr l2) acc))))))))
      (.isect lst-1-sorted lst-2-sorted '()))))

Simple tests:

(isect '(0 1 2 3 4 5 6) '(9 0 3 5 12 24 8 6))
;; => (0 3 5 6)

(isect '(#\a #\c #\h #\t #\e #\r #\b #\a #\h #\n) 
       '(#\a #\m #\s #\e #\l #\s #\t #\a #\r) 
       :equality-test #'char= 
       :sort-test #'char< 
       :key #'id)
;; => (#\a #\a #\e #\r #\t)

(isect '("this" "is" "just" "a" "boring" "test")
       '("this" "boring" "strings" "are" "to" "be" "intersected")
       :equality-test #'string= 
       :sort-test #'string< 
       :key #'id)
;; => ("boring" "this")

Upvotes: 0

Ehvince
Ehvince

Reputation: 18375

A built-in way (that won't work for homeworks ;) ) is to use intersection: https://lispcookbook.github.io/cl-cookbook/data-structures.html#intersection-of-lists

What elements are both in list-a and list-b ?

(defparameter list-a '(0 1 2 3))
(defparameter list-b '(0 2 4))
(intersection list-a list-b)
;; => (2 0)

Upvotes: 1

Aroob
Aroob

Reputation: 113

If you can ensure that the lists are sorted (ascending) you could do something like

(defun isect (l1 l2 acc)
  (let ((f1 (car l1))
        (f2 (car l2))
        (r1 (cdr l1))
        (r2 (cdr l2)))
    (cond ((or (null l1) (null l2)) acc)
          ((= f1 f2) (isect r1 r2 (cons f1 acc)))
          ((< f1 f2) (isect r1 l2 acc))
          ((> f1 f2) (isect l1 r2 acc)))))

Note though, that the result is in reversed order. Also, the example assumes that the elements are numbers. If you wanted to generalize, you could pass an ordering as an optional argument to make it work with arbitrary elements.

NB: A solution using loop would likely be faster but I could not think of how to partially "advance" the lists when the cars are different.

Upvotes: 0

Sylwester
Sylwester

Reputation: 48745

I assume isect with both arguments being the same list should return an equal list and not one that is flattened. In that case (append newlist x) is not adding an element to the end of a list. Here is my suggestion:

(defun intersect (lst-a lst-b &aux result)
  (dolist (a lst-a (nreverse result))
    (dolist (b lst-b)
      (when (equal a b)
        (push a result)))))

This is O(n^2) while you can do it in O(n) using a hash table.

Upvotes: 1

Related Questions