Recherche d'atomes dupliqués dans des listes éventuellement imbriquées dans LISP

Question

J'essaie de trouver comment trouver un atome dupliqué dans des listes éventuellement imbriquées. J'ai essayé de comprendre cela toute la journée. Si vous pouviez me donner la logique, ce serait génial parce que je veux vraiment apprendre.

essentiellement

(findDup '(a b b)) retournerait t

(findDup '(a c ((d (f a)) s))) redonnerait aussi t

Answer 1

Le serait la suivante (pseudocode) manière la plus simple et la plus efficace:

1. Créer une structure de données (comme la table de hachage du Common Lisp) pour se souvenir des atomes qui ont été vus
2. Créer une sous-fonction récursive qui fait le déplacement réel - marchant dans les listes imbriquées et en ajoutant tous les nouveaux atomes à la structure de données, et si l'on est déjà là, le retour vrai

Answer 2

Si la liste est vide/sans atomique car mais profondément vous allez (par exemple (car (car (car ...))) récursivement), alors la réponse est fausse.

Vous voulez trouver le premier atome de la liste, et voir si cet atome se trouve ailleurs dans la liste. Vous pouvez le faire avec une fonction comme member-of? -quelque chose de similaire est discuté dans Le Little Schemer, mais fondamentalement, vous venez de tester tous les atomes de la liste, et se reproduire sur les listes, contre cet atome.

Ensuite, si cet atome est dans la liste, vous pouvez renvoyer true.

Sinon, vous réessayez (récurrent) avec le cdr de la liste.

Answer 3

Je commencerais par une fonction wrapper qui crée une table de hachage et passe la table de hachage et la liste à une deuxième fonction (sinon, utilisez un argument &optional, si vous utilisez Common Lisp).

Ensuite, le pseudo-code suivant devrait être suffisant:

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 4

Cela devrait prendre en charge le premier cas:

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

Si la liste est triée ou peut être triée, c'est une solution simple:

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