时间戳

首页 > 解决方案 > 计算相等的元素

lisp - 计算相等的元素

问题描述

我有这个清单：

(2 2 2 2 3 4 4 5 5 5 6 7 7 7 8 8)

并想返回重复次数。结果应该是这样的：

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

标签： lispcommon-lisp

解决方案

这是您的函数，并带有一些注释：

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

该函数的目的是result通过递归调用occur-rec. 该last参数指示哪个是最后看到的值，并且counter是最后一个值的出现次数。

注意：

  • 当您调用时occur-rec，它会返回您想要返回的反向列表
  • 反转后的第一项将始终为零，因此您需要将其丢弃。

推荐阅读