HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Find all distinct triples less than N that sum to S

Submitted by: @import:stackexchange-codereview··
0
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.

(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.

(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.