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 (enumerate-integers i j)
  (if (= i j)
      (list j)
      (cons i (enumerate-integers (+ i 1) j))))

(define (filter f seq)
  (if (null? seq)
      (if (f (car seq)) 
          (cons (car seq) (filter f (cdr seq)))
          (filter f (cdr seq)))))

(define (remove x seq)
  (filter (if (pair? x) 
              (lambda (y) (not (member y x)))
              (lambda (y) (not (= x y)))) seq))

(define (unique-triples-less-than n)
  (let ((the-number-list (enumerate-integers 1 (- n 1))))
    (flatmap (lambda (i)
               (flatmap (lambda (j)
                          (map (lambda (k) (list i j k)) 
                               (remove (list i j) the-number-list))) 
                        (remove i the-number-list)))
             (enumerate-integers 1 (- n 1)))))

(define (flatmap f seq)
  (accumulate append null (map f seq)))

(define (accumulate op initial seq)
  (if (null? seq)
      (op (car seq) 
          (accumulate op initial (cdr seq)))))

(define (s-sum-triples-below-n n s)
  (filter (lambda (y) (= (accumulate + 0 y) s))
          (unique-triples-less-than n)))

Can this code be improved in any way?


Your unique-triples-less-than-n is unnecessarily complex because you can state it recursively. S. Kucherenko's answer tries to achieve this but is also unnecessarily complex. A simple recursive formulation is here, but this assumes that enumerate-integers returns an empty list if called with values from > to.

 (define (unique-tuples m from to)
    (if (= n 0) '(())) ; one empty tuple
        (flatmap (lambda (n)
                   (map (lambda (t) (cons n t))
                        (unique-tuples (- m 1) (+ n 1) to)))
                 (enumerate-integers from to))))

This unfolds as recursive calls e.g. like this:

 (u-t 3 1 4) = (flatmap ... '(1 2 3 4))
             = (flatten '(,(map (lambda (t) (cons 1 t))
                                (u-t 2 2 4))
                          ,(map (lambda (t) (cons 2 t)) ;; X
                                (u-t 2 3 4))
                          ,(map (lambda (t) (cons 2 t))
                                (u-t 2 4 4))
                          ,(map (lambda (t) (cons 2 t))
                                (u-t 2 5 4))))

and e.g. if you look at line marked with X, this takes recursively (unique-tuples 2 3 4), i.e. 2-tuples whose first integer is between 3 and 4, so the list is '((3 4)), and then for every element of that list, we add 2 at the beginning, so map returns '((2 3 4)).

Then just

(define (unique-triples n) (unique-tuples 3 1 n))

The results need to be filtered afterwards for the sum.

| improve this answer | |

Does this variant fit?

#lang racket
(define (filtered-by-sum-triples s n)
  (filter (sum-equal? s)
          (unique-triples n)))

(define (unique-triples n)
  (unique-sequences n 3))

(define (unique-sequences n arity)
  (define (rec num arity tail)
    (if (= arity 1)
        (map (lambda (x) (cons x tail))
             (enumerate-interval 1 num))
        (flatmap (lambda (x) (rec (sub1 x) (sub1 arity) (cons x tail)))
                 (enumerate-interval 1 num))))
  (rec n arity null))

(define (sum-equal? s)
  (lambda (sequence)
    (= (foldr + 0 sequence) s)))

(define (flatmap proc sequence) (foldr append null (map proc sequence)))

(define (enumerate-interval low high)
  (if (> low high)
      (cons low (enumerate-interval (add1 low) high))))
| improve this answer | |

The way I understand it, the exercise asked for ordered triples, that meant:

(i, j, k) foreach 0 < i <= j <= k <= n

Therefore, you could use the unique-pairs procedure,defined in the previous exercise, to come up with something simple like this:

    (lambda (a)
        (map (lambda (b) (cons a b))
             (unique-pairs (- a 1))))
(enumerate-interval 1 n))

If you don't want to modify your code, you could always filter away the results who aren't ordered, but that's just a waste of CPU cycles.

Other than that, procedures like filter or remove are builtin procedures in the Scheme interpreter I'm using (MIT/GNU Scheme). I don't know if they're part of the standard, but in any case I don't feel you should have to redefine them every time you post an exercise solution :)

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.