(sicp23)m2.61~m2.62

今度はソートされている集合の話

(use pre-sicp)

(define (element-of-set? x set)
  (cond ((null? set) #f)
        ((= x (car set) #t))
        ((< x (car set)) #f)
        (else (element-of-set? x (cdr set)))))

(define (intersection-set set1 set2)
  (if (or (null? set1) (null? set2))
      '()
      (let ((x1 (car set1)) (x2 (car set2)))
        (cond ((= x1 x2)
               (cons x1
                     (intersection-set (cdr set1)
                                       (cdr set2))))
              ((< x1 x2)
               (intersection-set (cdr set1) set2))
              ((< x2 x1)
               (intersection-set set1 (cdr set2)))))))

(intersection-set '(1 2 3 4) '(2 4 6 8))
;;	 gosh> (2 4)

;;m2.61
(define (adjoin-set x set)
  (if (< x (car set))
      (cons x set)
      (cons (car set) (adjoin-set x (cdr set)))))

;; 順序づけられていない場合、要素が集合内に存在していないかどうか調べるには、
;; その集合内のすべての要素を調べなければならない。
;; 一方、順序づけられていた場合、最低でも加えたい要素以下の数が存在しないことを確かめれば済む。
;; （これで、おおよそ半分ぐらいのステップ数で済む）

(adjoin-set 3 '(1 2 4))
;;	 gosh> (1 2 3 4)


;;m2.62
(define (union-set set1 set2)
      (cond ((null? set1) set2)
            ((null? set2) set1)
            (else
             (let ((x1 (car set1))(x2 (car set2)))
               (cond 
                ((= x1 x2)
                 (cons x1 (union-set (cdr set1) (cdr set2))))
                ((< x1 x2)
                 (cons x1 (union-set (cdr set1) set2)))
                ((< x2 x1)
                 (cons x2 (union-set set1 (cdr set2)))))))))

;; letの位置が重要。
;; (elseの前につけてしまうと、最後にset1もしくはset2が空になったときに,
;; 「pair required, but got ()」というエラーがでてしまう。)

;; あとは、O(n)かどうかについて考える。
;; どちらかの集合がnullである場合を除くと、行われる処理は3種類存在する。
;; この3種類の処理は最低でもset1,2のどちらかの要素数が1つ減る。
;; 比較は現在さしている要素（x1とx2）だけですむので、
;; ステップ数の最大は (+ (length set1) (length set2))になる。
;; なのでたぶんO(n)を満たしている。

(union-set '(1 2 3 4 5) '(2 4 6 8))
;;	 gosh> (1 2 3 4 5 6 8)