Elisp：如何查找列表重复项
Elisp: how to find list duplicates
我正在使用它来查找列表重复项：
(defun have-dups (x)
(let ((dups (copy-tree x)))
(if (eq (length (delete-dups dups)) (length x))
nil
t)))
(have-dups (list 1 2 3 3)) ;=> t
(have-dups (list 1 2 3)) ;=> nil
考虑到 copy-tree 和 delete-dups 的开销，可能有更好的方法。
使用散列 table，只要您发现散列 table 中已经存在的元素，您就知道您有重复项：
(defun has-dup (list)
(block nil
(let ((hash (make-hash-table :test 'eql)))
(map ()
(lambda (item)
(if (gethash item hash)
(return t)
(setf (gethash item hash) t)))
list))))
这是您的答案的简短版本，它使用 remove-duplicates 而不是 delete-dups，以避免后者的破坏性：
(defun has-dups-p (LIST) ""
(let ((unique1 (remove-duplicates LIST :test #'equal)))
(if (eq LIST unique1)
nil
t)))
(has-dups '(1 2 3 2 1)) ; t
(has-dups '("a" "b" "c")) ; nil
我发现这相当容易阅读，并且 eq 应该相当有效，因为它直接进入 C，特别是在列表早期出现重复的情况下。 remove-duplicates 和 delete-dups 都传递给 cl--delete-duplicates，这相当复杂...
随后是更长的解决方案，returns LIST 的元素有重复项，每个 duplicated[=] 的 position LIST 中的 35=] 元素（记住 seq 在 elisp 中是零索引的）。请注意，这目前仅适用于 LIST 的元素是 string 的情况，尽管我确信它可以进一步扩展到更一般的情况：
(defun list-duplicates (LIST) "
Returns `nil' when LIST has no duplicates.
Otherise, returns a `list' of `cons's.
In each list element:
- the `car' is the element of LIST which has duplicates.
- the `cdr' is a list of the positions where the duplicates are found."
(interactive)
;; res1 = result
;; unique1 = LIST with duplicates removed
(let ((unique1 (remove-duplicates LIST :test #'string-equal))
(res1 '()))
(if (eq LIST unique1)
nil
(progn
(dolist (x unique1)
;; i = incrementor
;; pos1 = list of postions of duplicates
(let (y (i 0) (pos1 '()))
(while (member x LIST)
(set 'y (seq-position LIST x))
(when (> i 0)
(push y pos1))
(set 'i (+ 1 i))
(set 'LIST
(substitute (concat x "1") x LIST :test #'string-equal :count 1)))
(push (cons x (nreverse pos1)) res1)))
(nreverse res1)))))
例如
(list-duplicates '("a" "b" "c")) ; nil
(list-duplicates '("a" "b" "b" "a" "b" "c" "c")) ; (("a" 3) ("b" 2 4) ("c" 6))
我正在使用它来查找列表重复项：
(defun have-dups (x)
(let ((dups (copy-tree x)))
(if (eq (length (delete-dups dups)) (length x))
nil
t)))
(have-dups (list 1 2 3 3)) ;=> t
(have-dups (list 1 2 3)) ;=> nil
考虑到 copy-tree 和 delete-dups 的开销，可能有更好的方法。
使用散列 table，只要您发现散列 table 中已经存在的元素，您就知道您有重复项：
(defun has-dup (list)
(block nil
(let ((hash (make-hash-table :test 'eql)))
(map ()
(lambda (item)
(if (gethash item hash)
(return t)
(setf (gethash item hash) t)))
list))))
这是您的答案的简短版本，它使用 remove-duplicates 而不是 delete-dups，以避免后者的破坏性：
(defun has-dups-p (LIST) ""
(let ((unique1 (remove-duplicates LIST :test #'equal)))
(if (eq LIST unique1)
nil
t)))
(has-dups '(1 2 3 2 1)) ; t
(has-dups '("a" "b" "c")) ; nil
我发现这相当容易阅读，并且 eq 应该相当有效，因为它直接进入 C，特别是在列表早期出现重复的情况下。 remove-duplicates 和 delete-dups 都传递给 cl--delete-duplicates，这相当复杂...
随后是更长的解决方案，returns LIST 的元素有重复项，每个 duplicated[=] 的 position LIST 中的 35=] 元素（记住 seq 在 elisp 中是零索引的）。请注意，这目前仅适用于 LIST 的元素是 string 的情况，尽管我确信它可以进一步扩展到更一般的情况：
(defun list-duplicates (LIST) "
Returns `nil' when LIST has no duplicates.
Otherise, returns a `list' of `cons's.
In each list element:
- the `car' is the element of LIST which has duplicates.
- the `cdr' is a list of the positions where the duplicates are found."
(interactive)
;; res1 = result
;; unique1 = LIST with duplicates removed
(let ((unique1 (remove-duplicates LIST :test #'string-equal))
(res1 '()))
(if (eq LIST unique1)
nil
(progn
(dolist (x unique1)
;; i = incrementor
;; pos1 = list of postions of duplicates
(let (y (i 0) (pos1 '()))
(while (member x LIST)
(set 'y (seq-position LIST x))
(when (> i 0)
(push y pos1))
(set 'i (+ 1 i))
(set 'LIST
(substitute (concat x "1") x LIST :test #'string-equal :count 1)))
(push (cons x (nreverse pos1)) res1)))
(nreverse res1)))))
例如
(list-duplicates '("a" "b" "c")) ; nil
(list-duplicates '("a" "b" "b" "a" "b" "c" "c")) ; (("a" 3) ("b" 2 4) ("c" 6))