list - 查找每个数字在列表中出现的次数

Question

如果我们有一个包含 (1 2 1 1 2 3 3 4 4 4) 的列表 A，我们如何获得一个新列表 B 中包含 ((1 . 30) (2 . 20) (3 . 20) (4 . 30))，这样 number_after_dot 就是列表 A 中的 number_before_dot。

例如1是列表A的30%，2是列表A的20%，等等..

(1 . 30) 是一对，可以通过 (cons 1 30)

Answer 1

我想你想要做的是计算列表中每个元素相等的百分比。您使用了“独特”一词，但由于您的列表没有独特元素，所以有点令人困惑。这是基于您的示例输入和输出，其中列表 (1 2 1 1 2 3 3 4 4 4) 由“30% ones”组成。

您可以将其大致分解为包含以下步骤的递归算法:

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 来获取它出现的次数:

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