3

如果我们有一个列表A持有(1 2 1 1 2 3 3 4 4 4)，我们怎么能得到一个新的列表B，((1 . 30) (2 . 20) (3 . 20) (4 . 30))其中number_after_dot是number_before_dot在列表中的百分比A。

例如1是 list 的 30% A， 2是 list 的 20% A，等等。

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

4

2 回答 2

2

问题表述非常接近游程编码的概念。在运行长度编码方面，您可以使用一个简单的策略：

  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))
于 2011-03-26T14:15:06.413 回答
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)获得最终列表的对。

要进行第二步，我们可以使用removewhich 的倒数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))) ; ***
于 2011-01-25T17:42:43.097 回答