my attempt to do the exercises in sicp.

Thursday, July 17, 2008

sicp exercise 2.41



;  Exercise 2.41. Write a procedure to find all ordered triples of distinct positive integers
;  i, j, and k less than or equal to a given integer n that sum to a given integer s.

(define (accumulate op init seq)
  (cond ((null? seq) init)
        (else (op (car seq) (accumulate op init (cdr seq))))))

(define (map1 op seq)
  (cond ((null? seq) (list))
        (else (cons (op (car seq)) (map1 op (cdr seq))))))

(define (flatmap oper seq) (accumulate append (list) (map oper seq)))

(define (filter1 pred seq)
  (cond ((null? seq) (list))
        ((pred (car seq)) (cons (car seq) (filter1 pred (cdr seq))))
        (else (filter1 pred (cdr seq)))))

(define (enumerate-n start end)
  (cond ((> start end) (list))
        (else (cons start (enumerate-n (+ 1 start) end)))))

(define (doubles n)
  (flatmap
    (lambda (x)
      (map
        (lambda (y) (list y x))
        (enumerate-n 1 (- x 1))))
    (enumerate-n 1 n)))


(define (triples n)
  (accumulate append (list)
    (flatmap
      (lambda (x)
        (map
          (lambda (y)
    (map
              (lambda (z) (list z y x))
              (enumerate-n 1 (- y 1))))
          (enumerate-n 1 (- x 1))))
      (enumerate-n 1 n))))

(define (triples-sum-less-than n sum)
  (filter1 (lambda (x)
             (>= sum (+ (car x) (cadr x) (caddr x))))
           (triples n)))

(display (doubles 7)) (newline)
(display (triples 6)) (newline)
(display (triples-sum-less-than 6 12)) (newline)

1 comment:

Rahul said...

Its better if we write code like generating n-let. Actually this generates nCr combination.
So problem could be extended to generating nCr combinations.