SICPを読む(71) 問題2.59 - 2.60 順序づけられないリストとしての集合

次は集合の表現に入ります。微分よりましかな。

集合について

Rubyの方がちょっとわかりやすい。

和集合
[1, 2, 3] | [3, 4, 5]
#=> [1, 2, 3, 4, 5]
積集合
[1, 2, 3] & [3, 4, 5]
#=> [3]

Rubyは集合に強いね。

特徴

特徴として、順序が無いってこと。

[3, 4, 5] | [1, 2, 3]
#=> [3, 4, 5, 1, 2]

うん、バラバラ。

順序づけられないリストってことがよくわかった。


では、例題で積集合を作ったので、練習問題で和集合を作ってみる。

問題 2.59

積集合の逆をやればいい。

(define (union-set set1 set2)
  (cond ((null? set1) set2)
        ((element-of-set? (car set1) set2)
         (union-set (cdr set1) set2))
        (else
          (cons (car set1)
                (union-set (cdr set1) set2)))))

set2の中に無かったら、リストに追加。

テストしてみる。

<union-set>--------------------------------------------------------------------
test data, expects (1 2 3 4) ==> ok
test (union-set '() '()), expects () ==> ok
test (union-set '() data), expects (1 2 3 4) ==> ok
test (union-set data '()), expects (1 2 3 4) ==> ok
test (union-set data data), expects (1 2 3 4) ==> ok
test (union-set data '(3 4 5 6)), expects (1 2 3 4 5 6) ==> ok
test (union-set '(3 4 5 6) data), expects (5 6 1 2 3 4) ==> ok
passed.

うまくいってる様子。


別解も思いついた。

(define (union-set set1 set2)
  (fold-right (lambda (a b)
                (ajoin-set a b))
              set2 set1))

fold-rightとajoin-setを使えばいい。


別解2

(define (union-set set1 set2)
  (if (null? set1)
      set2
      (ajoin-set (car set1)
                 (union-set (cdr set1) set2))))

順序が関係ないので、末尾再帰や、foldでも書ける。


やべぇ。回答集よりセクシーに書けてるぜ!!

問題 2.60

そのままでOK。ステップ数はデータ数に比例する。

つまり、重複を許す設計となっているので、直すべきは、例題と,問題2.59である!

重複を無くすには?

重複を許さない為にはどうすべきか・・・うぅん。

ユニーク?

(define (unique list)
  (fold-right
    (lambda (a b)
      (if (member a b)
          b
          (cons a b)))
    '() list))

(unique '(2 3 4 1 1 2 2)) ; (3 4 1 2)

intaraction-set,union-setした後で、ユニーク化(笑

ユニーク化した後で、ユニークしながら・・・あぁ、イマイチ!

結論

重複を許さない方が大変なので、重複を許した方が、早い。

重複を許さない場合は次節の様に、ソート済みのデータを扱った方が良い。


ということで、回答は次節へ持ち越し!!