Duplikate in einer Liste melden?

7

F: Wie erhalte ich nur die doppelten Elemente in einer Liste?

delete-dups(und cl-delete-duplicates) löscht alle doppelten Elemente aus einer Liste:

(delete-dups '(a b c c d d))            ; => '(a b c d)

Ich möchte das Gegenteil: Gibt es eine Funktion, die nur die Duplikate in einer Liste zurückgibt ?

(mystery-function '(a b c c d d))       ; => '(c d)
Dan
quelle

Antworten:

6

Ich denke, der einfachste Weg ist die Verwendung von Hash-Tabellen :

(defun get-duplicates (list &optional test)
  (let ((ht (make-hash-table :test (or test #'equal))) 
        ret)
    (dolist (x list)
      (incf (gethash x ht 0)))
    (maphash (lambda (key value)
               (when (> value 1)
                 (push key ret)))
             ht)
    ret))
(get-duplicates '(a 2 a b 3 2))
==> (2 a)
sds
quelle
Fwiw gibt es eine markierte Version von defun, die Schlüsselwortargumente akzeptiert.
YoungFrog
6

Verwenden des Bindestrichs:

(defun find-duplicates (list)
  "Return a list that contains each element from LIST that occurs more than once."
  (--> list
       (-group-by #'identity it)
       (-filter (lambda (ele) (> (length ele) 2)) it)
       (mapcar #'car it)))

Eine schnelle Testsuite:

(ert-deftest nothing ()
  (should-not (find-duplicates '())))

(ert-deftest no-duplicates ()
  (should-not (find-duplicates '(1 2 3 4 5 6 7 "eight"))))

(ert-deftest single-duplicate ()
  (should (equal (find-duplicates '(1 2 3 4 1))
                 '(1))))

(ert-deftest multiple-duplicates ()
  (should (equal (sort (find-duplicates '(1 2 3 4 1 6 7 8 9 2))
                       #'<)
                 '(1 2))))

(ert-deftest string-duplicates ()
  (should (equal (find-duplicates '(1 2 "three" 4 "three"))
                 '("three"))))

Es scheint derzeit, dass die Elemente in der Reihenfolge des ersten Auftretens jedes Duplikats zurückgegeben werden, aber ich sehe nichts -group-by, was dies garantiert, daher denke ich nicht, dass man sich darauf verlassen kann. Es könnte möglicherweise effizienter sein, Hashtabellen zu verwenden, aber das funktioniert.

zck
quelle
3

Hier ist eine Nicht-Hash-Version:

#+BEGIN_SRC emacs-lisp
(defun find-duplicates (list)
  (loop for (item . count) in (let ((counts '())
                    place)
                (dolist (el list)
                  (setq place (assoc el counts))
                  (if place
                      (incf (cdr place))
                    (push (cons el 1) counts)))
                counts)
    if (> count 1)
    collect item))
#+END_SRC
John Kitchin
quelle
0

Umkehren delete-dupsmit ... delete-dups(und seq):

(defun report-dups (list)
  (delete-dups (seq-filter
                (lambda (el) (member el (cdr (member el list))))
                list)))
caseneuve
quelle
0

Dies ähnelt der Definition von @ caseneuve.

(defun report-dups (xs)
  (delete-dups (cl-remove-if-not (lambda (x) (member x (cdr (member x xs)))) xs)))

Beide leiden jedoch unter dem Testen jedes Elements in der Liste, selbst wenn es bereits getestet wurde. Und dann rennen sie delete-dups.

Diese Definition ist unkompliziert und leidet nicht unter diesen Ineffizienzen:

(defun report-dups (xs)
  (let ((ys  ()))
    (while xs
      (unless (member (car xs) ys) ; Don't check it if already known to be a dup.
        (when (member (car xs) (cdr xs)) (push (car xs) ys)))
      (setq xs  (cdr xs)))
    ys))

Es scheint auch ungefähr 6-mal schneller zu sein als die Hash-Table-Lösung ( get-duplicatesoben).

Drew
quelle