SICPを読む(71) 問題2.59 - 2.60 順序づけられないリストとしての集合
次は集合の表現に入ります。微分よりましかな。
集合について
Rubyの方がちょっとわかりやすい。
和集合
[1, 2, 3] | [3, 4, 5] #=> [1, 2, 3, 4, 5]
特徴
特徴として、順序が無いってこと。
[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した後で、ユニーク化(笑
ユニーク化した後で、ユニークしながら・・・あぁ、イマイチ!
結論
重複を許さない方が大変なので、重複を許した方が、早い。
重複を許さない場合は次節の様に、ソート済みのデータを扱った方が良い。
ということで、回答は次節へ持ち越し!!