LISP: Как проверить, имеют ли два списка одинаковые элементы?

Question

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

Например: (ABCDEF) и (BEAFDC) имеют одни и те же элементы (ноль) и (ноль) имеют одни и те же элементы

(ABCDEF) и (АБВГДЕЖ) не имеют одни и те же элементы

Проблема в том, что я знаю только некоторые основные команды, и я могу использовать только те. Это почти все команды, которые я знаю:

CAR, CDR, LENGTH, NULL, MEMBER, NOT, AND, OR, NOT, MAPCAR, APPLY, DO, SETQ, LET 

я написал следующую функцию до сих пор, но я не знаю, как проверить наличие дубликатов членов, и это не работает должным образом для всех списков, Я хочу проверить:

(defun same-elem-p (lst1 lst2) 
    (cond ((not (null lst1)) 
     (cond ((member (car lst1) lst2) 
       (same-elem-p (cdr lst1) lst2)) 
       (t nil))) 
     (t t))) 

Надеюсь, я объяснил проблему достаточно хорошо.

Answer 1

Вы можете определить функцию, которая возвращает истину, если список содержит еще одно:

(defun member (x liste) 
    (cond 
     ((null liste)()) 
     ((equal (car liste) x) liste) 
     (t (member x (cdr liste))))) 

(defun inclus (liste1 liste2) 
    (cond 
     ((null liste1) t) 
     ((member (car liste1) liste2)(inclus (cdr liste1) liste2)) 
     (t()))) 

Затем использовать его, чтобы определить, являются ли два списка равны:

(defun compare (liste1 liste2) 
    (if ((and (inclus liste1 liste2) (inclus liste2 liste1))) 
     (print "the 2 lists are equivalent") 
     (print "the 2 lists aren't equivalent"))) 

Answer 2

Написать функцию, которая сопоставляет над list1 и для каждого элемента в list1

1. находит его в list2. Если он отсутствует в списке2, то он терпит неудачу.
2. в противном случае он удаляет его из list2

Answer 3

Если ваши элементы являются числами или если у вас есть достойный компаратор для элементов (в данном случае это будет алфавитный порядок), вы можете просто y используйте процедуру сортировки для обоих списков, а затем проверьте, совпадают ли они.

Теоретически сложность всей операции будет вокруг O (N log (N)) (поскольку реализация Lisp «sort» очень хороша). Что касается ответа Хеди, то сложность была бы такой, как O (N²/2) (потому что «член» будет называться N раз, и каждый вызов со средним временем (N/2)).

Answer 4

Обработка списка в качестве набора, и если вы можете использовать несколько команд, как:

INTERSECTION SET-DIFFERENCE EQ 

Вы можете определить эту функцию:

(defun equal-lists (list1 list2) 
(and (eq (null (intersection list1 list2)) nil) 
(null (set-difference list1 list2)))) 

Тогда, если пересечение не пустое множество, и различию пусто, set1 равно set2.

Answer 5

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

(defun same-elements (lst1 lst2) 
    (and (= (length lst1) (length lst2)) 
     (every #'(lambda (x) (member x lst2)) 
       lst1) 
     (every #'(lambda (x) (member x lst1)) 
       lst2))) 

Например:

CL-USER> (same-elements '(a b c) '(c a b)) 
T 

Обратите внимание, что этот код не будет обрабатывать все обстоятельства. Например, он вернет T, когда два разных элемента повторяются в двух списках, как в (a b b c) и (a a b c). Но, по большей части, он выполняет свою работу.

Answer 6

(defun same (a b) 
`(cond 
((null a)'same) 
((member(car a) b) (same(cdr a) b)) 
(t'nosame))) 

(defun entre () 
(let((a) (b)) 
(princ " list a : ") (setq a (read)) 
(princ " list b : ") (setq b (read)) 
(if (= (length a) (length b)) (same a b) 'nosame))) 

Answer 7

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

(defun same-elements (l1 l2) 
    (and (subsetp l1 l2) (subsetp l2 l1)))