sicp-ex-2.62



<< Previous exercise (2.61) | Index | Next exercise (2.63) >>


shyam

Exercise 2.62. Give a Θ(n) implementation of union-set for sets represented as ordered lists.

  
  
  
  
 (define (union-set set1 set2) 
   (cond  ((null? set1) set2) 
          ((null? set2) set1) 
          ((= (car set1) (car set2))  
           (cons (car set1) (union-set (cdr set1) (cdr set2)))) 
          ((< (car set1) (car set2))   
           (cons (car set1) (union-set (cdr set1) set2))) 
          (else  
           (cons (car set2) (union-set set1 (cdr set2)))))) 
  

Or, If you want to make it ugly saving 5 car operations on a run,

  
 (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))) 
                   (else (cons x2 (union-set set1 (cdr set2))))))))) 
  


Christian-Delahousse

Here's a slightly more elegant solution using ajoint-set from the previous exercise.

  
  
  
  
 ;From ex. 2.61 
 (define (adjoin-set x set) 
   (cond ((null? set) (list x)) 
         ((= x (car set)) set)  
         ((> x (car set))  
          (cons (car set) (adjoin-set x (cdr set)))) 
         ((< x (car set)) 
          (cons x set)) 
         (else (error "WTF!?")))) 
  
 ;Answer 
 (define (union-set s1 s2) 
   (cond ((null? s1) s2) 
         ((element-of-set? (car s1) s2) 
          (union-set (cdr s1) s2)) 
         (else (union-set (cdr s1) (adjoin-set (car s1) s2))))) 
  

This solution is not O(n) though. adjoin-set and union-set are O(n). If you call either one for each n, the solution becomes O(n²).

Here's my solution. Is basically the same as the first one, but more elegant.

 (define (union-set-2 set1 set2) 
   (cond ((null? set1) set2) 
         ((null? set2) set1) 
         (else 
           (let ((x1 (car set1)) 
                 (x2 (car set2))) 
             (cons (min x1 x2) 
                   (union-set-2 (if (> x1 x2) 
                                  set1 
                                  (cdr set1)) 
                                (if (> x2 x1) 
                                  set2 
                                  (cdr set2)))))))) 



category-learning-scheme