Лисп / Пересечение Списков

Question

Здравствуйте, я пытаюсь создать функцию в common-lisp , которая принимает два списка и выводит их пересечения, предполагая, что в каждом списке нет повторений без использования функции пересечения. Кажется, это не работает. Кто-нибудь может помочь?

(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)))
        )
    )
)

Answer 1

;; 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 '()))))

Простые тесты:

(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")

Answer 2

Если вы можете убедиться, что списки отсортированы (по возрастанию), вы можете сделать что-то вроде

(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)))))

Обратите внимание, что результат находится в обратном порядке.Также в примере предполагается, что элементы являются числами.Если вы хотите обобщить, вы можете передать порядок в качестве необязательного аргумента, чтобы заставить его работать с произвольными элементами.

Примечание: решение, использующее loop, вероятно, будет быстрее, но я не мог придумать, как частично«продвигать» списки, когда car s отличаются.

Answer 3

Встроенный способ (который не будет работать для домашних заданий;)) должен использовать intersection: https://lispcookbook.github.io/cl-cookbook/data-structures.html#intersection-of-lists

Какие элементы есть и в list-a, и в list-b?

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

Answer 4

Я предполагаю, что isect с обоими аргументами, являющимися одним и тем же списком, должен возвращать равный список, а не тот, который сведен.В этом случае (append newlist x) не добавляет элемент в конец списка.Вот мое предложение:

(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)))))

Это O (n ^ 2), в то время как вы можете сделать это в O (n), используя хеш-таблицу.