Найти, сколько раз один номер встречается в списке

Question

Если бы у нас было list A (1 2 1 1 2 3 3 4 4 4), как мы могли бы получить новое list B ( (1 . 30) (2 . 20) (3 . 20) (4 . 30))? Если number_before_dot является% number_before_dot в списке A`. Например, 30 - это% 1 в списке A, 20% 2 в списке A .. и т. Д. (1. 30) - это пара, которую можно составить из (минусов 1 30)

Answer 1

Формулировка вопроса очень близка к идее кодирование длин серий .С точки зрения кодирования длин серий вы можете использовать простую стратегию:

1. Сортировка.
2. Кодирование длин серий.
3. Масштабирование длин серий для получения процентов.

Вы можете реализовать кодирование длин серий следующим образом:

(define (run-length-encode lst)
  (define (rle val-lst cur-val cur-cnt acc)
    (if (pair? val-lst)
        (let ((new-val (car val-lst)))
          (if (eq? new-val cur-val)
              (rle (cdr val-lst) cur-val (+ cur-cnt 1) acc)
              (rle (cdr val-lst) new-val 1 (cons (cons cur-val cur-cnt) acc))))
        (cons (cons cur-val cur-cnt) acc)))
  (if (pair? lst)
      (reverse (rle (cdr lst) (car lst) 1 '()))
      '()))

и масштабирование выглядит следующим образом:

(define (scale-cdr count-list total-count)
  (define (normalize pr)
    (cons (car pr) (/ (* 100 (cdr pr)) total-count)))
  (map normalize count-list))

Теперь нам нужно что-то для сортировки списка.Я просто использую функцию sort в ракетке (адаптируюсь по мере необходимости).Функция для вычисления процентов для каждого числа в списке:

(define (elem-percent lst)
  (scale-cdr (run-length-encode (sort lst <)) (length lst)))

Некоторые примеры использования:

> (elem-percent '())
'()
> (elem-percent (list 1 2 3 4 5))
'((1 . 20) (2 . 20) (3 . 20) (4 . 20) (5 . 20))
> (elem-percent (list 1 2 1 1))
'((1 . 75) (2 . 25))
> (elem-percent (list 1 2 1 1 2 3 3 4 4 4))
'((1 . 30) (2 . 20) (3 . 20) (4 . 30))

Answer 2

Я думаю, что вы хотите вычислить процентную долю списка, равную каждому элементу. Вы использовали слово «уникальный», но это немного сбивает с толку, поскольку в вашем списке нет уникальных элементов. Это основано на ваших примерах ввода и вывода, где список (1 2 1 1 2 3 3 4 4 4) состоит из "30% единиц".

Вы можете грубо разбить это на рекурсивный алгоритм, состоящий из следующих шагов:

1. Если список ввода пуст, вернуть пустой список.
2. В противном случае получите первый элемент. Подсчитайте, сколько раз это встречается в списке.
3. Рассчитайте процент и cons элемент с этим процентом.
4. Удалить все вхождения первого элемента из cdr списка.
5. Запишитесь в этом новом списке и cons составьте список из (element . percentage) пар.

Для выполнения первой части давайте используем filter:

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

С вашим списком A это вернет список (1 1 1). Затем мы можем использовать длину, чтобы узнать, сколько раз это произошло:

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

Чтобы рассчитать процент, разделите на количество элементов во всем списке или (length A) и умножьте на 100:

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

Это просто cons с помощью элемента (car A), чтобы получить пару для окончательного списка.

Чтобы сделать второй шаг, мы можем использовать remove, обратное filter: он вернет список всех элементов исходного списка, которые не удовлетворяют функции предиката:

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

Это список, в который мы хотим вернуться. Обратите внимание, что на каждом шаге вы должны иметь исходный список (или длину исходного списка) и этот новый список. Поэтому вам нужно как-то сделать это доступным для рекурсивной процедуры, либо с помощью дополнительного аргумента, либо с помощью определения внутреннего определения.

Может быть, есть более эффективные способы, я уверен, или просто другие способы, но это было решением, которое я нашел, когда читал вопрос. Надеюсь, это поможет!

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