patternMinor
Find all distinct triples less than N that sum to S
Viewed 0 times
distinctsumalltriplesthanlessthatfind
Problem
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.
Can this code be improved in any way?
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?
Solution
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.
This unfolds as recursive calls e.g. like this:
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
The results need to be filtered afterwards for the sum.
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.
Code Snippets
(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))))(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))))(define (unique-triples n) (unique-tuples 3 1 n))Context
StackExchange Code Review Q#1845, answer score: 3
Revisions (0)
No revisions yet.