Search for duplicate atoms in possibly nested lists in LISP

Question

I am trying to figure out how to find a duplicated atom in possibly nested lists. I tried to figure it out all day. If you could explain the logic to me, that would be great, because I really want to learn.

primarily

(findDup '(a b b)) will return t

(findDup '(a c ((d (f a)) s))) will also return t

Answer 1

The simplest and most effective way is the following (pseudo-code):

• Create a data structure (such as a shared Lisp hash table) to remember which atoms were seen
• Create a recursive subfunction that performs the actual move - move the nested lists and add all new atoms to the data structure, and if it already exists, returns true

Answer 2

, :

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

/ car, (, (car (car (car ...))) ), .

, . member-of? -something, " ", , .

, , true.

, (recur on) cdr .

Answer 5

I would start with a wrapper function that creates a hash table and passes a hash table and a list of the second function (alternatively, use the argument &optionalif you use Common Lisp).

Then the following pseudo-code should be sufficient:

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 a duplicate if it already in the hash table. If not, add it to the hash table and inspect the tail for duplicates.