lisp - 查找出现次数最多的列表并返回以出现次数最多的元素开头的列表

Question

(defun occurrences (l)
(let (
        (result (mapcar #'(lambda (elt) (cons elt (count elt l)) ) 
            (remove-duplicates l)   )   )
        (result2 nil)  
        (result3 nil)
        (result4 nil)
    )
(progn
    (sort result #'> :key #'cdr)
    (loop for x in result
        do (and(push (car x) result2)(push (cdr x) result3))
    )
)))

这应该返回一个按升序排列的排序列表。除了重复最少次数的元素(与列表的其余部分相一致)外，不应返回。除非所有元素重复相同次数，否则只有在这种情况下才会返回所有元素。

例如，

1. ( occurrences '(1 2 3)) => (1 2 3)，#notice 每个元素重复相同的 # 次。

2. ( occurrences '(1 1 3)) => (1) #因为 1 出现的频率比列表中的任何其他元素都高。

3 ( 出现次数 '(1 2 3 4 6 6 6 6)) => (6)

1. ( 出现次数 '(1 1 3 3 0)) => (1, 3)。 #since (1 2), (3 2) 和 (0 1)因为元素 1 和 3 的出现次数仍然高于该列表中至少一个元素的出现次数。

注意:现在这个函数返回一个排序列表，但错误地返回最大值(occ. 的数量)加上出现的元素不至少大于列表中的另一个元素。前任。(occurrences '(7 7 7 1 2 3)) 返回 (7 1 2 3) 但应该只返回 7。我真的很感激能帮助修复此函数以返回预期的结果。

Answer 1

使用您的初始方法的解决方案如下:

(defun max-occurrences(l)
  (let* ((occurrences (remove-duplicates 
                        (mapcar #'(lambda (elt) (cons elt (count elt l))) l) 
                        :test 'equal))
         (max-occurrence (reduce #'max occurrences :initial-value 0 :key #'cdr)))
    (mapcar #'car (remove-if-not (lambda(x) (= x max-occurrence)) occurrences :key #'cdr))))

然而，这个解决方案效率不高，因为它的成本为 O(n²)(在初始阶段，列表中的每个元素都与所有其他元素进行比较以计算其频率).

已编辑

例如通过使用哈希表可以获得更有效的解决方案(@uselpa 在评论中建议改进):

(defun max-occurrences(l)
   (let* ((table (make-hash-table))
          (max-count (loop for elt in l maximize (incf (gethash elt table 0)))))
     (loop for elt being the hash-key of table using (hash-value count)
        when (= count max-count) collect elt)))