7

Q: how do I get only the duplicate elements in a list?

delete-dups (and cl-delete-duplicates) deletes all duplicate elements from a list:

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

I want the reverse: is there a function that returns only the duplicates in a list?

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

I think the easiest way is to use hash tables:

(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)
  • Fwiw there's a starred version of defun which accepts keyword arguments. – YoungFrog Mar 14 '17 at 16:01
6

Using dash:

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

A quick test suite:

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

It currently seems to return the items in the order of the first occurrence of each duplicate, but I don't see anything in -group-by that guarantees that, so I don't think that can be relied on. It could possibly be more efficient, using hashtables, but this works.

3

Here is a non-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
0

Reversing delete-dups using... delete-dups (and seq):

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

This is similar to @caseneuve's definition.

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

But both suffer from testing each element in the list, even if it has already been tested. And then they run delete-dups.

This definition is straightforward, and it doesn't suffer from those inefficiencies:

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

It also seems to be about 6 times faster than the hash-table solution (get-duplicates, above).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.