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.

I modeled my answer after the procedure `prime-sum-pairs`

from my answer to the previous exercise:

```
(define (prime-sum-pairs n)
(map make-pair-sum
(filter prime-sum?
(unique-pairs n))))
```

The procedure for this exercise is `triple-sum`

:

```
(define (triple-sum n s)
(filter (lambda (seq) (sequence-sum? seq s))
(unique-triples n)))
```

The first argument, `n`

, is the number that the numbers in the triple have to be less than or equal to. The second argument, `s`

, is the target sum. `unique-triples`

finds all ordered triples of distinct positive integers i, j, and k less than or equal to a given integer `n`

. Then `sequence-sum?`

is used to filter that list of ordered triples to keep only the ones that add up to the given integer `s`

.

Note that an analogue to `make-pair-sum`

isn’t needed because that was used only to stick the sum onto the end of each ordered pair. For this exercise, we don’t need to stick anything onto the end of the ordered triple.

Also note that I used a `lambda`

function to enclose `sequence-sum`

in order to pass the target sum `s`

to it.

### Enumerating all the unique triples with `unique-triples`

Here’s `unique-pairs`

:

```
(define (unique-pairs n)
(flatmap (lambda (i)
(map (lambda (j) (list i j))
(enumerate-interval 1 (- i 1))))
(enumerate-interval 1 n)))
```

To write `unique-triples`

, start with the innermost part of `unique-pairs`

, except change the letters and make a triple instead of a pair:

`(map (lambda (k) (list i j k)) (enumerate-interval 1 (- j 1)))`

This produces a list of triples `(i j k)`

that start with a given `i`

and a given `j`

, where 0 < `k`

< `j`

.

Example:

```
(define i 5)
(define j 4)
(define test1 (map (lambda (k) (list i j k)) (enumerate-interval 1 (- j 1))))
```

```
> test1
((5 4 1) (5 4 2) (5 4 3))
```

Next, for a given `i`

, take the sequence representing `j`

going from 1 to `i`

-1 and `flatmap`

it onto the above, to give a list of triples for each `j`

with 0 < `j`

< `i`

:

```
(flatmap (lambda (j)
(map (lambda (k) (list i j k)) (enumerate-interval 1 (- j 1))))
(enumerate-interval 1 (- i 1)))
```

Example:

```
(define i 5)
(define test2
(flatmap (lambda (j)
(map (lambda (k) (list i j k)) (enumerate-interval 1 (- j 1))))
(enumerate-interval 1 (- i 1))))
```

```
> test2
((5 2 1) (5 3 1) (5 3 2) (5 4 1) (5 4 2) (5 4 3))
```

The last step is to take the sequence representing `i`

going from 1 to `n`

and `flatmap`

it onto the previous `flatmap`

, to give that list of triples for each `i`

from 1 to `n`

. Then you have `unique-triples`

:

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

```
> (unique-triples 3)
((3 2 1))
> (unique-triples 4)
((3 2 1) (4 2 1) (4 3 1) (4 3 2))
> (unique-triples 5)
((3 2 1) (4 2 1) (4 3 1) (4 3 2) (5 2 1) (5 3 1) (5 3 2) (5 4 1) (5 4 2) (5 4 3))
```

### The filter procedure `sequence-sum?`

`sequence-sum?`

is used in this exercise for triples, but I wrote it to be more generally usable for a sequence of any length. The first argument `seq`

is a sequence of numbers. The second argument `sum`

is the target sum. If the numbers in the sequence add up to the target sum, the procedure returns `#t`

; otherwise it returns `#f`

.

```
(define (sequence-sum? seq sum)
(equal? sum (accumulate + 0 seq)))
```

```
> (sequence-sum? (list 1 2 3) 6)
#t
> (sequence-sum? (list 1 2 3) 5)
#f
> (sequence-sum? (list 1 2 3 4 5 6 7 8) 36)
#t
> (sequence-sum? (list 1 2 3 4 5 6 7 8) 46)
```

### Testing `triple-sum`

```
(define (triple-sum n s)
(filter (lambda (seq) (sequence-sum? seq s))
(unique-triples n)))
```

```
> (triple-sum 4 6)
((3 2 1))
> (triple-sum 5 7)
((4 2 1))
> (triple-sum 5 8)
((4 3 1) (5 2 1))
```

### Other procedures needed to get these to run:

```
(define (enumerate-interval low high)
(if (> low high)
nil
(cons low (enumerate-interval (+ low 1) high))))
(define (flatmap proc seq)
(accumulate append nil (map proc seq)))
(define (accumulate op initial sequence)
(if (null? sequence)
initial
(op (car sequence)
(accumulate op initial (cdr sequence)))))
(define (filter predicate sequence)
(cond ((null? sequence) nil)
((predicate (car sequence))
(cons (car sequence)
(filter predicate (cdr sequence))))
(else (filter predicate (cdr sequence)))))
```

### Not needed for this exercise: `unique-tuples`

I also wrote `unique-tuples`

, a general case procedure of `unique-pairs`

and `unique-triples`

, for tuples of any given length. `n`

is the maximum value of the elements of the tuples and `k`

is the length of the tuples. I assumed that `n`

and `k`

are integers.

The procedure uses recursion on both the maximum value of an entry and the length of the tuple.

```
(define (unique-tuples n k)
(cond ((< k 1) (list nil))
((< n 1) nil)
((< n k) nil)
(else (flatmap (lambda (i)
(map (lambda (l) (cons i l))
(unique-tuples (- i 1) (- k 1))))
(enumerate-interval 1 n)))))
```

```
> (unique-tuples 3 2)
((2 1) (3 1) (3 2))
> (unique-tuples 2 3)
()
> (unique-tuples 3 0)
(())
> (unique-tuples 0 3)
()
```