牌語備忘録 -pygo

あくまでもメモです。なるべくオフィシャルの情報を参照してください。

牌語備忘録 -pygo

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

(define (adjoin-set x set)
  (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 (left-branch tree) (cadr tree))
(define (right-branch tree) (caddr 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

def adjoin_set(x, set):
    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