计数相等的元素
Count equal elements
我有这个列表：
(2 2 2 2 3 4 4 5 5 5 6 7 7 7 8 8)
并想return重复的次数。结果应该是这样的：
(4 1 2 3 1 3 2)
我试过递归方法，但没有成功。我不确定这是正确的方法。
首先我做了一个函数来计算元素是否相等：
(defun count-until-dif (alist)
(1+ (loop for i from 0 to (- (length alist) 2)
while (equal (nth i alist) (nth (1+ i) alist))
sum 1)))
然后递归函数（不工作！）：
(defun r-count-equal-elem (alist)
(cond
((NULL alist) nil)
((NULL (car alist)) nil)
((NULL (cadr alist)) nil)
((equal (car alist) (cadr alist))
(cons (count-until-dif alist) (r-count-equal-elem (cdr alist)))
)
(t (cons 1 (r-count-equal-elem (cdr alist)) )
) ) )
一种天真的方法如下：
(2 2 2 2 3 4 4 5 5 5 6 7 7 7 8 8)
首先，使用函数 (remove-duplicates '(1 2 2 3)) 获取唯一编号列表，其中 returns (1 2 3)
(2 3 4 5 6 7 8)
然后对于每个数字，您计算它们在第一个列表中出现的次数：
(let ((repetitions '()))
(dolist ((value unique-list))
(let ((count (count-if (lambda (x)
(= x value))
initial-list)))
(push count repetitions))))
一种直接的方法是使用 count-if to count the number of appearances made by the first element of the list, and nthcdr 递归输入列表以减少列表。这仅适用于元素组合在一起的列表，如 OP 示例输入中所示。
(defun count-reps (xs)
(if (endp xs)
'()
(let ((count (count-if #'(lambda (x) (eql x (car xs))) xs)))
(cons count (count-reps (nthcdr count xs))))))
CL-USER> (count-reps '(2 2 2 2 3 4 4 5 5 5 6 7 7 7 8 8))
(4 1 2 3 1 3 2)
这是一个替代解决方案，它在不使用 count-if 的情况下递归构建计数列表：
(defun count-reps (xs)
(if (endp xs)
'()
(let ((rest-counts (count-reps (cdr xs))))
(if (eql (car xs) (cadr xs))
(cons (1+ (car rest-counts))
(cdr rest-counts))
(cons 1 rest-counts)))))
此处 rest-counts 表示列表其余部分的计数列表。当列表的第一个元素和列表的第二个元素为eql时，第一个计数递增；否则遇到一个新元素并且 1 被 cons 编入计数列表。
您发布的解决方案从正确的方向开始，但递归函数 r-count-equal-elem 有点偏离轨道。您不需要使用 null 检查那么多情况，也没有理由检查 equal 的元素，因为您已经在 count-until-dif 中这样做了。事实上，使用 count-until-dif，您可以通过与上面第一个解决方案非常相似的方式解决问题：
(defun r-count-equal-elem (alist)
(if (null alist)
'()
(let ((count (count-until-dif alist)))
(cons count
(r-count-equal-elem (nthcdr count alist))))))
这是带有一些注释的函数：
(defun r-count-equal-elem (alist)
(cond
((NULL alist) nil)
;; the two tests below are not necessary in my opinion,
;; the fact that the list may contain NIL elements should
;; be a separate problem, as a first draft you can avoid it
((NULL (car alist)) nil)
((NULL (cadr alist)) nil)
;; what you should be testing is if the cddr is NULL, this would
;; tell you that there is only one remaining element in the list.
((equal (car alist) (cadr alist))
;; you cons the count with a recursive result computed just
;; one place after the current one, but if you have a repetition of
;; N times value V, the recursive count will contain N-1 repetitions
;; of V, etc. you have to advance in the list by N for the recursive
;; case
(cons (count-until-dif alist) (r-count-equal-elem (cdr alist)))
)
;; this looks like a corner case that could be merged
;; with the general case above.
(t (cons 1 (r-count-equal-elem (cdr alist)) )
) ) )
此外，辅助函数有点低效：
(defun count-until-dif (alist)
;; each time you call count-until-dif you compute the length
;; of the linked list, which needs to traverse the whole list.
;; you generally do not need to know the length, you need to know
;; if there is a next element or not to guard your iteration.
(1+ (loop for i from 0 to (- (length alist) 2)
while (equal (nth i alist) (nth (1+ i) alist))
sum 1)))
我建议编写一个如下所示的函数 occur-rec：
(defun occur-rec (list last counter result)
(if (null list)
....
(destructuring-bind (head . tail) list
(if (equal head last)
(occur-rec ... ... ... ...)
(occur-rec ... ... ... ...)))))
最初使用输入列表调用函数，last 看到的值绑定到 nil，当前 counter 设置为零，result nil.
该函数的目的是通过 occur-rec 的递归调用将结果的反转构建到 result 中。 last 参数表示哪个是最后看到的值，counter 是最后一个值出现的次数。
注意：
- 当您调用
occur-rec 时，它 return 是您想要 return 的反向列表
- 反转后的第一项永远为零，所以你需要丢弃它。
我还会添加 reduce:
的功能性（ish）变体
(defun runs (data &key (test #'eql))
(when data
(flet ((add-item (res-alist x)
(if (funcall test x (caar res-alist))
(progn (incf (cdar res-alist))
res-alist)
(cons (cons x 1) res-alist))))
(nreverse (reduce #'add-item (cdr data)
:initial-value (list (cons (car data) 1)))))))
CL-USER> (runs '(2 2 2 2 3 4 4 5 5 5 6 7 7 7 8 8) :test #'=)
;;=> ((2 . 4) (3 . 1) (4 . 2) (5 . 3) (6 . 1) (7 . 3) (8 . 2))
CL-USER> (mapcar #'cdr (runs '(2 2 2 2 3 4 4 5 5 5 6 7 7 7 8 8) :test #'=))
;;=> (4 1 2 3 1 3 2)
使用loop：
(defun count-reps (list)
(loop for count from 1
for (curr next) on list
unless (eql curr next)
collect (shiftf count 0)))
文字相同；在一个循环中，设置一个从 1 开始的自动递增计数器 COUNT，并选择参数列表的连续子列表的第一个 (CURR) 和第二个元素 (NEXT)，忽略列表的其余部分。当第一个 (CURR) 和第二个 (NEXT) 元素不同时（或者因为不同的数字，或者我们在 NEXT 为 nil 的末尾），将 COUNT 的值存储在结果列表中，并将 COUNT 设置为 0.
使用 mapl 的 lispier 版本，类似于 loop 的“for ... on list”服务于列表的连续 cdr：
(defun count-reps (list &aux (counter 0) (result (list)))
(mapl (lambda (head)
(incf counter)
(unless (eql (first head) (second head))
(push (shiftf counter 0) result)))
list)
(reverse result))
我有这个列表：
(2 2 2 2 3 4 4 5 5 5 6 7 7 7 8 8)
并想return重复的次数。结果应该是这样的：
(4 1 2 3 1 3 2)
我试过递归方法，但没有成功。我不确定这是正确的方法。
首先我做了一个函数来计算元素是否相等：
(defun count-until-dif (alist)
(1+ (loop for i from 0 to (- (length alist) 2)
while (equal (nth i alist) (nth (1+ i) alist))
sum 1)))
然后递归函数（不工作！）：
(defun r-count-equal-elem (alist)
(cond
((NULL alist) nil)
((NULL (car alist)) nil)
((NULL (cadr alist)) nil)
((equal (car alist) (cadr alist))
(cons (count-until-dif alist) (r-count-equal-elem (cdr alist)))
)
(t (cons 1 (r-count-equal-elem (cdr alist)) )
) ) )
一种天真的方法如下：
(2 2 2 2 3 4 4 5 5 5 6 7 7 7 8 8)
首先，使用函数 (remove-duplicates '(1 2 2 3)) 获取唯一编号列表，其中 returns (1 2 3)
(2 3 4 5 6 7 8)
然后对于每个数字，您计算它们在第一个列表中出现的次数：
(let ((repetitions '()))
(dolist ((value unique-list))
(let ((count (count-if (lambda (x)
(= x value))
initial-list)))
(push count repetitions))))
一种直接的方法是使用 count-if to count the number of appearances made by the first element of the list, and nthcdr 递归输入列表以减少列表。这仅适用于元素组合在一起的列表，如 OP 示例输入中所示。
(defun count-reps (xs)
(if (endp xs)
'()
(let ((count (count-if #'(lambda (x) (eql x (car xs))) xs)))
(cons count (count-reps (nthcdr count xs))))))
CL-USER> (count-reps '(2 2 2 2 3 4 4 5 5 5 6 7 7 7 8 8))
(4 1 2 3 1 3 2)
这是一个替代解决方案，它在不使用 count-if 的情况下递归构建计数列表：
(defun count-reps (xs)
(if (endp xs)
'()
(let ((rest-counts (count-reps (cdr xs))))
(if (eql (car xs) (cadr xs))
(cons (1+ (car rest-counts))
(cdr rest-counts))
(cons 1 rest-counts)))))
此处 rest-counts 表示列表其余部分的计数列表。当列表的第一个元素和列表的第二个元素为eql时，第一个计数递增；否则遇到一个新元素并且 1 被 cons 编入计数列表。
您发布的解决方案从正确的方向开始，但递归函数 r-count-equal-elem 有点偏离轨道。您不需要使用 null 检查那么多情况，也没有理由检查 equal 的元素，因为您已经在 count-until-dif 中这样做了。事实上，使用 count-until-dif，您可以通过与上面第一个解决方案非常相似的方式解决问题：
(defun r-count-equal-elem (alist)
(if (null alist)
'()
(let ((count (count-until-dif alist)))
(cons count
(r-count-equal-elem (nthcdr count alist))))))
这是带有一些注释的函数：
(defun r-count-equal-elem (alist)
(cond
((NULL alist) nil)
;; the two tests below are not necessary in my opinion,
;; the fact that the list may contain NIL elements should
;; be a separate problem, as a first draft you can avoid it
((NULL (car alist)) nil)
((NULL (cadr alist)) nil)
;; what you should be testing is if the cddr is NULL, this would
;; tell you that there is only one remaining element in the list.
((equal (car alist) (cadr alist))
;; you cons the count with a recursive result computed just
;; one place after the current one, but if you have a repetition of
;; N times value V, the recursive count will contain N-1 repetitions
;; of V, etc. you have to advance in the list by N for the recursive
;; case
(cons (count-until-dif alist) (r-count-equal-elem (cdr alist)))
)
;; this looks like a corner case that could be merged
;; with the general case above.
(t (cons 1 (r-count-equal-elem (cdr alist)) )
) ) )
此外，辅助函数有点低效：
(defun count-until-dif (alist)
;; each time you call count-until-dif you compute the length
;; of the linked list, which needs to traverse the whole list.
;; you generally do not need to know the length, you need to know
;; if there is a next element or not to guard your iteration.
(1+ (loop for i from 0 to (- (length alist) 2)
while (equal (nth i alist) (nth (1+ i) alist))
sum 1)))
我建议编写一个如下所示的函数 occur-rec：
(defun occur-rec (list last counter result)
(if (null list)
....
(destructuring-bind (head . tail) list
(if (equal head last)
(occur-rec ... ... ... ...)
(occur-rec ... ... ... ...)))))
最初使用输入列表调用函数，last 看到的值绑定到 nil，当前 counter 设置为零，result nil.
该函数的目的是通过 occur-rec 的递归调用将结果的反转构建到 result 中。 last 参数表示哪个是最后看到的值，counter 是最后一个值出现的次数。
注意：
- 当您调用
occur-rec时，它 return 是您想要 return 的反向列表
- 反转后的第一项永远为零，所以你需要丢弃它。
我还会添加 reduce:
(defun runs (data &key (test #'eql))
(when data
(flet ((add-item (res-alist x)
(if (funcall test x (caar res-alist))
(progn (incf (cdar res-alist))
res-alist)
(cons (cons x 1) res-alist))))
(nreverse (reduce #'add-item (cdr data)
:initial-value (list (cons (car data) 1)))))))
CL-USER> (runs '(2 2 2 2 3 4 4 5 5 5 6 7 7 7 8 8) :test #'=)
;;=> ((2 . 4) (3 . 1) (4 . 2) (5 . 3) (6 . 1) (7 . 3) (8 . 2))
CL-USER> (mapcar #'cdr (runs '(2 2 2 2 3 4 4 5 5 5 6 7 7 7 8 8) :test #'=))
;;=> (4 1 2 3 1 3 2)
使用loop：
(defun count-reps (list)
(loop for count from 1
for (curr next) on list
unless (eql curr next)
collect (shiftf count 0)))
文字相同；在一个循环中，设置一个从 1 开始的自动递增计数器 COUNT，并选择参数列表的连续子列表的第一个 (CURR) 和第二个元素 (NEXT)，忽略列表的其余部分。当第一个 (CURR) 和第二个 (NEXT) 元素不同时（或者因为不同的数字，或者我们在 NEXT 为 nil 的末尾），将 COUNT 的值存储在结果列表中，并将 COUNT 设置为 0.
使用 mapl 的 lispier 版本，类似于 loop 的“for ... on list”服务于列表的连续 cdr：
(defun count-reps (list &aux (counter 0) (result (list)))
(mapl (lambda (head)
(incf counter)
(unless (eql (first head) (second head))
(push (shiftf counter 0) result)))
list)
(reverse result))