# 2.3.3 Example: Representing SetsをPythonでやってみた

SICP2.3.3 Example: Representing Sets あたりを Python でやってみた

##### scheme (original code)

Scheme(Gauche)でfalseとtrueを使うとエラーになるから、#fと#tに変えてやってみた

```;2.3.3  Example: Representing Sets
;Sets as unordered lists

(define (element-of-set? x set)
;  (cond ((null? set) false)
(cond ((null? set) #f)
;        ((equal? x (car set)) true)
((equal? x (car set)) #t)
(else (element-of-set? x (cdr set)))))
;test
(element-of-set? 1 '(1 2 3));#t
(element-of-set? 1 '(4 5 6));#f
(element-of-set? 1 '(4 5 6 1));#t

(if (element-of-set? x set)
set
(cons x set)))
;test
(adjoin-set 1 '(1 2 3)) ;(1 2 3)
(adjoin-set 1 '(4 5 6)) ;(1 4 5 6)

(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))))
;test
(intersection-set '(1 2 3) '(4 5 6))   ;()
(intersection-set '(1 2 3 4 5) '(1 2)) ;(1 2)
(intersection-set '(4 5) '(4 5 6))     ;(4 5)

;Sets as ordered lists
(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)))))
;test
(element-of-set? 1 '(4 5 6)) ;#f
(element-of-set? 5 '(4 5 6)) ;#t
(element-of-set? 9 '(4 5 6)) ;#f

(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)))))))
;test
(intersection-set '(1 2 3) '(4 5 6))   ;()
(intersection-set '(1 2 3 4 5) '(1 2)) ;(1 2)
(intersection-set '(4 5) '(4 5 6))     ;(4 5)

;Sets as binary trees
(define (entry tree) (car tree))
(define (make-tree entry left right)
(list entry left right))

(define (element-of-set? x set)
(cond ((null? set) #f)
((= x (entry set)) #t)
((< x (entry set))
(element-of-set? x (left-branch set)))
((> x (entry set))
(element-of-set? x (right-branch set)))))
;test
(element-of-set? 7 '(7 '('(3 '(1 5)) '(9 '11))))   ;#t
(element-of-set? 3 '(3 '('(1) '(7 '(5 '(9 11)))))) ;#t
(element-of-set? 5 '(5 '('(3 '1) '(9 '(7 11)))))   ;#t
```
##### python
```#2.3.3  Example: Representing Sets
#Sets as unordered lists

def element_of_set(x, set):
if not set:
return False
if x == set[0]:
return True
else:
return element_of_set(x, set[1:])
#test
print element_of_set(1, [1,2,3]) #True
print element_of_set(1, [4,5,6]) #False
print element_of_set(1, [4,5,6,1]) #True

if element_of_set(x, set):
return set
return [x] + set
#test
print adjoin_set(1, [1,2,3]) #[1, 2, 3]
print adjoin_set(1, [4,5,6]) #[1, 4, 5, 6]

def intersection_set(set1, set2):
if not set1 or not set2:
return []
if element_of_set(set1[0], set2):
return [set1[0]] + intersection_set(set1[1:], set2)
else:
return intersection_set(set1[1:], set2)
#test
print intersection_set([1, 2, 3], [4, 5, 6])    #[]
print intersection_set([1, 2, 3, 4, 5], [1, 2]) #[1, 2]
print intersection_set([4, 5], [4, 5, 6])       #[4, 5]

#Sets as ordered lists
def element_of_set_q(x, set):
if not set:
return False
if x == set[0]:
return True
if x < set[0]:
return False
else:
return element_of_set_q(x, set[1:])
#test
print element_of_set_q(1, [4,5,6]) #False
print element_of_set_q(5, [4,5,6]) #True
print element_of_set_q(9, [4,5,6]) #False

def intersection_set(set1, set2):
if not set1 or not set2:
return []
x1 = set1[0]
x2 = set2[0]
if x1 == x2:
return [x1] + intersection_set(set1[1:], set2[1:])
if x1 < x2:
return intersection_set(set1[1:], set2)
if x2 < x1:
return intersection_set(set1, se2[1:])
#test
print intersection_set([1,2,3], [4,5,6]) #[]
print intersection_set([1,2,3,4,5], [1,2]) #[1, 2]
print intersection_set([4,5], [4,5,6]) #[4, 5]

#Sets as binary trees
def entry(tree):
return tree[0]
def left_branch(tree):
return tree[1]
def right_branch(tree):
return tree[2]
def make_tree(entry, left, right):
return [entry, left, right]

def element_of_set_q(x, set):
if not set:
return False
if x == entry(set):
return True
if x < entry(set):
return element_of_set_q(x, left_branch(set))
if x > entry(set):
return element_of_set_q(x, right_branch(set))
#test
print element_of_set_q(7, [7, [[3, [1, 5]], [9,[11]]]])  #True
print element_of_set_q(3, [3, [[1], [7, [5, [9, 11]]]]]) #True
print element_of_set_q(5, [5, [[3,[1]], [9, [7, 11]]]])  #True
```