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

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

Например: (A B C D E F) и (B E A F D C) имеют одинаковые элементы (nil) и (nil) имеют одинаковые элементы

(A B C D E F) и (A B C D E F G) не имеют одинаковых элементов

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

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

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


list equality lisp
person seby598    schedule 02.04.2013    source источник

Ответы (7)


arrow_upward
5
arrow_downward

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

(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")))
person Kira    schedule 02.04.2013
comment
Спасибо за Ваш ответ. Можно ли было бы написать все это в одной функции? Мне было интересно, почему вы написали функцию-член; его еще нет в LISP? - person seby598; 02.04.2013
comment
Конечно, есть способ, но я не думаю, что он будет простым! и да, функция-член уже существует, но я забыл об этом. Больше года я не программировал на LISP. - person Kira; 03.04.2013

arrow_upward
2
arrow_downward

Два списка содержат одни и те же элементы, если каждый элемент одного списка является элементом другого списка, и наоборот. Предполагая, что вы можете использовать функцию 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). Но, по большей части, он делает свою работу.

person Andrea S.    schedule 19.03.2016

arrow_upward
1
arrow_downward

Напишите функцию, которая отображает список1 и каждый элемент в списке1.

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

arrow_upward
1
arrow_downward

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

INTERSECTION SET-DIFFERENCE EQ

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

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

Тогда, если пересечение не является пустым множеством, а разность пуста, множество1 равно множеству2.

person user3194191    schedule 28.04.2014

arrow_upward
1
arrow_downward

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

(defun same-elements (l1 l2)
  (and (subsetp l1 l2) (subsetp l2 l1)))
person Benjamin Kuykendall    schedule 02.04.2017

arrow_upward
0
arrow_downward

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

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

person user2116758    schedule 27.11.2013

arrow_upward

arrow_downward

person    schedule
comment
Пожалуйста, отредактируйте с дополнительной информацией. Ответы только на код и попробуйте эти ответы не рекомендуются, потому что они не содержат содержимого для поиска и не объясняют, почему кто-то должен попробовать это. - person abarisone; 22.07.2016