0

英語が下手で申し訳ありません..リスト内のすべての値の出現回数をカウントし、 次のようなドット ペアのリストを返す
「make-bag」という関数を作成するタスクがあります: '((value1 . num-occurences1)
(value2 . num-occurences2) ...) 例: 

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

(リストはソートする必要はありません)

私たちの講師は、関数MAPCARand も(実装されていると仮定して) 使用できるようにしていますが、 and のFILTER使用は許可されていません。彼はまた、再帰を使用することを要求しています。REMOVE-DUPLICATESCOUNT-IF

重複を削除せずにすべての値を 1 回だけカウントする方法はありますか? 方法があれば、再帰によって実行できますか?

4

2 に答える 2

2

まず、Joswig 氏に同意します。Stackoverflow は宿題の答えを求める場所ではありません。ただし、追加の掘り下げと、ハッシュテーブルと字句閉鎖がどのように機能するかを理解できるようにしないと、直接使用できない可能性があるという方法であなたの質問に答えます。これは、あなたの進歩のための良い練習になります。

重複を削除せずにすべての値を 1 回だけカウントする方法はありますか? 方法があれば、再帰によって実行できますか?

はい、ハッシュテーブルを使用すると簡単です。2 つの例を次に示します。

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

ここで、このフォームを 2 回評価しようとすると、毎回同じ答えが得られます。

(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

そして、これは 2 番目の例です。

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

ここで、このフォームを 2 回評価しようとすると、2 回目の回答は 2 倍になります。

(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

なぜ答えが2倍になったのですか？

ハッシュテーブルの内容を連想リストに変換するには?

また、再帰関数は通常、リストを「食べる」ものであり、各ステップの結果を蓄積するアキュムレータを持っている場合があり、最後に返されることにも注意してください。ハッシュ テーブルと 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 に答える