Count equal elements

Question

I have this list:

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

and would like to return the number of repetitions. The result should be this:

(4 1 2 3 1 3 2)

I have tried a recursive approach, but with no success. I'm not sure this is the correct way to go.
First I made a function to count while elements are equal:

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

And then the recursive function (not working!):

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

Answer 1

Using loop:

(defun count-reps (list)
  (loop for count from 1
        for (curr next) on list
        unless (eql curr next)
        collect (shiftf count 0)))

The same in words; in a loop, set up an autoincrementing counter COUNT from 1, and pick the first (CURR) and second element (NEXT) of the consecutive sublists of the argument list, disregarding the rest of the list. When the first (CURR) and second (NEXT) elements differ (either because different numbers, or we're at the end where NEXT is nil), store the value of COUNT in a result list, and set COUNT to 0.

A lispier version using mapl, which like loop's "for ... on list" serves consecutive cdrs of the list:

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

Answer 2

i would also add functional(ish) variant with 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)

Answer 3

One straightforward approach is to recurse over the input list using count-if to count the number of appearances made by the first element of the list, and nthcdr to reduce the list. This will only work for lists with elements grouped together as in the OP example input.

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

Here is an alternate solution that recursively builds the list of counts without using 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)))))

Here rest-counts represents the list of counts for the rest of the list. When the first element of the list and the second element of the list are eql, the first count is incremented; otherwise a new element has been encountered and a 1 is consed onto the list of counts.

Your posted solution started in the right direction, but the recursive function r-count-equal-elem got a bit off-track. You don't need to check so many cases with null, and there is no reason to check elements for equal since you are already doing that in count-until-dif. In fact, using count-until-dif, you can solve the problem in a way very similar to the first solution above:

(defun r-count-equal-elem (alist)
  (if (null alist)
      '()
      (let ((count (count-until-dif alist)))
        (cons count
              (r-count-equal-elem (nthcdr count alist))))))

Answer 4

Here is your function annotated with some remarks:

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

Also, the helper function is a bit inefficient:

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

I'd suggest writing a function occur-rec that looks like this:

(defun occur-rec (list last counter result)
  (if (null list)
      ....
      (destructuring-bind (head . tail) list
        (if (equal head last)
            (occur-rec ... ... ... ...)
            (occur-rec ... ... ... ...)))))

The function is called initially with the input list, the last seen value being bound to nil, the current counter set to zero, and the result being nil.

The intent of the function is to build the reverse of the result into result, by recursive invocations of occur-rec. The last parameter indicates which is the last seen value, and counter is the number of occurrence for the last value.

Note that:

• when you call occur-rec, it returns the reversed list of what you want to return
• the first item after reversing will always be zero, so you need to discard it.

Answer 5

One naive approach could be the following:

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

First, get the list of unique numbers with the function (remove-duplicates '(1 2 2 3)) which returns (1 2 3)

(2 3 4 5 6 7 8)

Then for each number, you count how many times they appear in the first list:

(let ((repetitions '()))
  (dolist ((value unique-list))
    (let ((count (count-if (lambda (x)
                             (= x value))
                           initial-list)))
      (push count repetitions))))