# Find all distinct triples less than N that sum to S

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?

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.

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))))


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