0

我为糟糕的英语道歉。
我有一个任务是编写一个名为“make-bag”的函数，它计算列表中每个值的出现次数
并返回一个点对列表，如下所示：'((value1 . num-occurences1) (value2 . num-occurrences2) ...) 例如： 

 (make-bag '(d c a b b c a))
((d . 1) (c . 2) (a . 2) (b . 2))

（列表不必排序）

我们的讲师允许我们使用函数MAPCARand FILTER（假设已实现），但我们不允许使用REMOVE-DUPLICATESand COUNT-IF。他还要求我们使用递归。

有没有办法只计算每个值一次而不删除重复项？如果有办法，可以通过递归来完成吗？

4

2 回答 2

2

首先，我同意 Joswig 先生的观点 - Stackoverflow 不是要求家庭作业答案的地方。但是，我将以一种你可能无法直接使用它的方式回答你的问题，而无需进行一些额外的挖掘，并且能够理解哈希表和词法闭包的工作原理。反过来，这将是一个很好的锻炼你的进步。

有没有办法只计算每个值一次而不删除重复项？如果有办法，可以通过递归来完成吗？

是的，哈希表很简单，这里有两个例子：

;; no state stored
(defun make-bag (lst)
  (let ((hs (make-hash-table)))
    (labels ((%make-bag (lst)
               (if lst
                   (multiple-value-bind (val exists)
                       (gethash (car lst) hs)
                     (if exists
                         (setf (gethash (car lst) hs) (1+ val))
                         (setf (gethash (car lst) hs) 1))
                     (%make-bag (cdr lst)))
                   hs)))
      (%make-bag lst))))

现在，如果您尝试评估此表单两次，每次都会得到相同的答案：

(gethash 'a (make-bag '(a a a a b b b c c b a 1 2 2 1 3 3 4 5 55)))
> 5
> T

(gethash 'a (make-bag '(a a a a b b b c c b a 1 2 2 1 3 3 4 5 55)))
> 5
> T

这是第二个例子：

;; state is stored....
(let ((hs (make-hash-table)))
  (defun make-bag (lst)
    (if lst
        (multiple-value-bind (val exists)
            (gethash (car lst) hs)
          (if exists
              (setf (gethash (car lst) hs) (1+ val))
              (setf (gethash (car lst) hs) 1))
          (make-bag (cdr lst)))
        hs)))

现在，如果您尝试两次评估此表格，您将得到第二次加倍的答案：

(gethash 'x (make-bag '(x x x y y x z z z z x)))
> 5
> T

(gethash 'x (make-bag '(x x x y y x z z z z x)))
> 10
> T

为什么答案翻了一番？

如何将哈希表的内容转换为关联列表？

另请注意，递归函数通常会“吃”列表，有时还会有一个累加器，用于累加每一步的结果，并在最后返回。如果没有哈希表和使用 remove-duplicates/count-if 的能力，逻辑会变得有点复杂，因为您被迫使用基本功能。

于 2012-08-30T18:01:01.717 回答
1

好吧，这就是答案，但为了让它作为一个学习练习更有用，我会留下一些空白，你必须填写。

还要注意，对这个任务使用哈希表会更有利，因为对存储在哈希表中的元素的访问时间是固定的（通常非常小），而对存储在列表中的元素的访问时间具有线性复杂性，所以会随着更长的列表而增长。

(defun make-bag (list)
  (let (result)
    (labels ((%make-bag (list)
               (when list
                 (let ((key (assoc (car <??>) <??>)))
                   (if key (incf (cdr key))
                       (setq <??>
                             (cons (cons (car <??>) 1) <??>)))
                   (%make-bag (cdr <??>))))))
      (%make-bag list))
    result))

此功能可能有变体，但它们大致基于相同的原理。

于 2012-08-30T12:58:40.413 回答