Find all distinct triples less than N that sum to S

Question

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)
      null
      (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)
      initial
      (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?

Answer 1

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.

Answer 2

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)
      null
      (cons low (enumerate-interval (add1 low) high))))

Answer 3

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:

(flatmap
    (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 :)