Find how many times each number occurs in list

Question

If we had a list A holding (1 2 1 1 2 3 3 4 4 4), how could we get a new list B with ((1 . 30) (2 . 20) (3 . 20) (4 . 30)) in it, such that the number_after_dot is the percentage of the number_before_dot in the list A.

For example 1 is 30% of list A, 2 is 20% of list A, etc..

(1 . 30) is a pair, which could be made by (cons 1 30)

Answer 1

I think what you want to do is calculate the percentage of the list that is equal to each element. You used the word "unique" but that a bit confusing since your list has no unique elements. This is based on your sample input and output, where the list (1 2 1 1 2 3 3 4 4 4) is composed of "30% ones".

You can break this down roughly into a recursive algorithm consisting of these steps:

1. If the input list is empty, return the empty list.
2. Otherwise, get the first element. Calculate how many times it occurs in the list.
3. Calculate the percentage, and cons the element with this percentage.
4. Remove all the occurrences of the first item from the cdr of the list.
5. Recurse on this new list, and cons up a list of (element . percentage) pairs.

To do the first part, let's use filter:

> (filter (lambda (x) (eq? (car A) x)) A)
(1 1 1)

With your list A, this will return the list (1 1 1). We can then use length to get the number of times it occurs:

> (length (filter (lambda (x) (eq? (car A) x)) A))
3

To calculate the percentage, divide by the number of elements in the whole list, or (length A) and multiply by 100:

> (* 100 (/ (length (filter (lambda (x) (eq? (car A) x)) A)) (length A)))
30

It's easy to cons this with the element (car A) to get the pair for the final list.

To do the second step, we can use remove which is the inverse of filter: it will return a list of all elements of the original list which do not satisfy the predicate function:

> (remove (lambda (x) (eq? (car A) x)) A)
(2 2 3 3 4 4 4)

This is the list we want to recurse on. Note that at each step, you need to have the original list (or the length of the original list) and this new list. So you would need to somehow make this available to the recursive procedure, either by having an extra argument, or defining an internal definition.

There might be more efficient ways I'm sure, or just other ways, but this was the solution I came up with when I read the question. Hope it helps!

(define (percentages all)
  (let ((len (length all))) ; pre-calculate the length
    ;; this is an internal definition which is called at ***
    (define (p rest)
      (if (null? rest)
          rest
          ;; equal-to is a list of all the elements equal to the first
          ;; ie something like (1 1 1)
          (let ((equal-to (filter (lambda (x) (eq? (car rest) x))
                                  rest))
                ;; not-equal-to is the rest of the list
                ;; ie something like (2 2 3 3 4 4 4)
                (not-equal-to (remove (lambda (x) (eq? (car rest) x))
                                      rest)))
            (cons (cons (car rest) (* 100 (/ (length equal-to) len)))
                  ;; recurse on the rest of the list
                  (p not-equal-to)))))
    (p all))) ; ***