Lisp - элементы лиспа встречаются в другом списке

Question

У меня проблема с этой функцией lisp.Я хочу создать функцию, которая получает два списка и проверяет, присутствуют ли элементы первого списка (все они) во втором списке, и возвращает True, если это произойдет.

В настоящее время у меня есть следующий код:

(defun ocorre-listas (l1 l2)
(dolist (elem1 l1)
    (dolist (elem2 l2)
        (if (equal elem1 elem2)
            t))))

Это не работает, как ожидалось.Должен ли я попытаться сделать это с помощью простой рекурсии?Я действительно не понимаю, как я могу повторить оба списка в поисках равных элементов.

Я решил попробовать без долистов.Это то, что у меня сейчас, оно все еще не работает.

(defun ocorre-listas (l1 l2)
(cond ((null l1) nil)
        ((null l2) nil)
        ((if (/= (first l1)(first l2)) (ocorre-listas l1 (rest l2))))
        (t (if (= (first l1) (first l2)) (ocorre-listas (rest l1)(rest l2))))))

Я получаю предупреждение о том, что "t" - неопределенная функция.Кроме того, каждый пример, который я пробую, возвращает ноль.Что я делаю не так?

Answer 1

Так что вам нужно проверить, является ли every элемент l1 member l2. Обе эти функции входят в стандартную библиотеку Common Lisp, поэтому, если вам разрешено их использовать, вы можете с их помощью создать простое решение.

Answer 2

См. Общий список подмножество Предикат и его реализация:

CL-USER> (subsetp '(1 2 3) '(1 2 3 4)
T

Answer 3

Во втором фрагменте кода, если первый список пуст, то все его элементы находятся во втором.

Вам не нужно ifs, так как вы находитесь внутри cond

После проверки, если списки пусты, вам нужно будет только проверить, находится ли первый элемент первого списка во втором, и снова вызвать функцию с первым списком без этого элемента

Answer 4

Вместо того, чтобы пытаться делать все в одной функции, рассмотрите возможность разделения ее на две (или более) функции, например,

• , которая принимает число, а второй список и проверяет, появляется ли числов списке
• Другой, который перебирает числа в первом списке, и для каждого тестирует (используя первую функцию), появляется ли он во втором списке.

Такжекак DOLIST, рассмотрите возможность использования MAPCAR и FIND-IF (при условии, что они разрешены в этом назначении.)

Answer 5

Чтобы иметь возможность работать с обоими списками одновременно, уловка, вероятно, состоит в сортировке списков перед началом рекурсии.Тогда нужно будет просто сравнить первый элемент и рекурсивно применить ту же функцию к остальной части списка, добавив, конечно, немного магии CAR / CDR ...

Answer 6

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

вот функция объединения

(defun my-union (a b)
  (let ((h (make-hash-table :test #'equal)))
    (mapcar (lambda (x) (setf (gethash x h) x)) a)
    (mapcan (lambda (x) (when (gethash x h) (list x))) b)))

здесь тестирование функции для элементов IDENTICAL в обоих списках

(defun same-elements (a b)
  (apply #'= (mapcar #'length (list (my-union a b) a b))))

вот функция, обеспечивающая a подмножество b (то, что вы спросили)

(defun subset (a b)
  (same-elements (my-union a b) a))