Note: this wiki is now retired and will no longer be updated!

The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.

SICP exercise 2.41

From Drewiki
Jump to: navigation, search

Problem

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.

Solution

Here's a definition of such a procedure:

(define nil (quote ()))
 
(define (filter predicate sequence)
  (cond ((null? sequence) nil)
        ((predicate (car sequence))
         (cons (car sequence)
               (filter predicate (cdr sequence))))
        (else (filter predicate (cdr sequence)))))
 
(define (enumerate-interval low high)
  (if (> low high)
      nil
      (cons low (enumerate-interval (+ low 1) high))))
 
(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op initial (cdr sequence)))))
 
(define (flatmap proc seq)
  (accumulate append nil (map proc seq)))
 
(define (triples-that-sum-to s n)
  (define (sum-to-s? triple)
    (= s (+ (car triple) (cadr triple) (caddr triple))))
  (define (unique-triples n)
    (flatmap (lambda (i)
               (flatmap (lambda (j)
                          (map (lambda (k) (list i j k))
                               (enumerate-interval 1 (- j 1))))
                        (enumerate-interval 1 (- i 1))))
             (enumerate-interval 1 n)))
  (filter sum-to-s? (unique-triples n)))

Test:

(triples-that-sum-to 1 5)

Output:

()

(triples-that-sum-to 7 5)

Output:

((4 2 1))

(triples-that-sum-to 10 6)

Output:

((5 3 2) (5 4 1) (6 3 1))

Personal tools