Поиск дублирующих атомов в возможно вложенных списках в LISP

Question

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

в основном

(findDup '(a b b)) вернул бы t

(findDup '(a c ((d (f a)) s))) такжевозврат т

Answer 1

Если список отсортирован или может быть отсортирован, это простое решение:

(defun find-duplicates (lst)
   (let ((dup-list nil))
      (sort lst)
      (mapcon (lambda (l) (when (eq (car l) (cadr l)) (push (car l) dup-list))) lst)
      dup-list ))

Answer 2

Самый простой и эффективный способ - следующий (псевдокод):

1. Создание структуры данных (например, хеш-таблицы Common Lisp) для запоминания атомов, которые были замечены
2. Создайте рекурсивную подфункцию, которая выполняет фактический обход - обход вложенных списков и добавление всех новых атомов в структуру данных, и, если один из них уже существует, возвращает true

Answer 3

Это должно позаботиться о первом случае:

(defun find-duplicates (lst)
  (let ((h (make-hash-table))
        (dupes))
    (mapcar #'(lambda (x)
        (if (gethash x h)
              (push x dupes)
              (setf (gethash x h) t)))
        lst)
    dupes))

Answer 4

Я бы начал с функции-оболочки, которая создает хеш-таблицу и передает хеш-таблицу и список второй функции (в качестве альтернативы используйте аргумент &optional, если вы используете Common Lisp).

Тогда достаточно следующего псевдокода:

If we're looking at an empty list, there are no duplicates
If the head is a list, we can return the logical OR of "inspect the head" and "inspect the tail"
If the head is an atom, it's a duplicate if it's already in the hash table. If not, add it to the hash table and inspect the tail for duplicates.

Answer 5

Если список пуст / без атомарного car, как бы глубоко вы ни пошли (например, (car (car (car ...))) рекурсивно), тогда ответ ложный.

Вы хотите найти первый атом списка и посмотреть, встречается ли этот атом где-нибудь еще в списке. Вы можете сделать это с помощью функции, подобной member-of? - нечто подобное обсуждается в Little Schemer , но в основном вы просто проверяете все атомы в списке и повторяетесь в списках против этого атома.

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

Иначе, вы попытаетесь снова (повторить) с cdr в списке.