blob: b9193bd3f670f8cc1191644a929d98e9247c6e86 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
#lang racket
;; unordered distinct list
;; linear scan of the elements O(n)
(define (element-of-set? x myset)
(cond ((null? myset) false)
((equal? x (car myset)) true)
(else (element-of-set? x (cdr myset)))))
;; O(n)
(define (adjoin-set x myset)
(if (element-of-set? x myset)
myset
(cons x myset)))
;; linear scan of set1 and at each step we scan set2, O(n**2)
(define (intersection-set set1 set2)
(cond ((or (null? set1) (null? set2)) '())
((element-of-set? (car set1) set2)
(cons (car set1)
(intersection-set (cdr set1) set2)))
(else (intersection-set (cdr set1) set2))))
(intersection-set (list 1 2 3) (list 'a 2 'c))
;; linear scan of set1 and at each step we scan set2, O(n**2)
(define (union-set set1 set2)
(cond ((null? set1) set2)
((null? set2) set1)
((not (element-of-set? (car set1) set2))
(cons (car set1)
(union-set (cdr set1) set2)))
(else (union-set (cdr set1) set2))))
(union-set (list 1 2 3) (list 2 3 'c))
|
