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

Question

this is the exercise 2.41 in SICP I have wrote this naive version myself:

(defn sum-three [n s]
  (for [i (range n)
        j (range n)
        k (range n)
        :when (and (= s (+ i j k))
                   (< 1 k j i n))]
    [i j k]))

The question is: is this considered idiomatic in clojure? And how can I optimize this piece of code? since it takes forever to compute(sum-three 500 500)

Also, how can I have this function take an extra argument to specify number of integer to compute the sum? So instead of sum of three, It should handle more general case like sum of two, sum of four or sum of five etc.

I suppose this cannot be achieved by using for loop? not sure how to add i j k binding dynamically.

Answer 1

(Update: The fully optimized version is sum-c-opt at the bottom.)

I'd say it is idiomatic, if not the fastest way to do it while staying idiomatic. Well, perhaps using == in place of = when the inputs are known to be numbers would be more idiomatic (NB. these are not entirely equivalent on numbers; it doesn't matter here though.)

As a first optimization pass, you could start the ranges higher up and replace = with the number-specific ==:

(defn sum-three [n s]
  (for [k (range n)
        j (range (inc k) n)
        i (range (inc j) n)
        :when (== s (+ i j k))]
    [i j k]))

(Changed ordering of the bindings since you want the smallest number last.)

As for making the number of integers a parameter, here's one approach:

(defn sum-c [c n s]
  (letfn [(go [c n s b]
            (if (zero? c)
            [[]]
            (for [i  (range b n)
                  is (go (dec c) n (- s i) (inc i))
                  :when (== s (apply + i is))]
              (conj is i))))]
    (go c n s 0)))

;; from the REPL:
user=> (sum-c 3 6 10)
([5 4 1] [5 3 2])
user=> (sum-c 3 7 10)
([6 4 0] [6 3 1] [5 4 1] [5 3 2])

Update: Rather spoils the exercise to use it, but math.combinatorics provides a combinations function which is tailor-made to solve this problem:

(require '[clojure.math.combinatorics :as c])

(c/combinations (range 10) 3)
;=> all combinations of 3 distinct numbers less than 10;
;   will be returned as lists, but in fact will also be distinct
;   as sets, so no (0 1 2) / (2 1 0) "duplicates modulo ordering";
;   it also so happens that the individual lists will maintain the
;   relative ordering of elements from the input, although the docs
;   don't guarantee this

filter the output appropriately.

A further update: Thinking through the way sum-c above works gives one a further optimization idea. The point of the inner go function inside sum-c was to produce a seq of tuples summing up to a certain target value (its initial target minus the value of i at the current iteration in the for comprehension); yet we still validate the sums of the tuples returned from the recursive calls to go as if we were unsure whether they actually do their job.

Instead, we can make sure that the tuples produced are the correct ones by construction:

(defn sum-c-opt [c n s]
  (let [m (max 0 (- s (* (dec c) (dec n))))]
    (if (>= m n)
      ()
      (letfn [(go [c s t]
                (if (zero? c)
                  (list t)
                  (mapcat #(go (dec c) (- s %) (conj t %))
                          (range (max (inc (peek t))
                                      (- s (* (dec c) (dec n)))) 
                                 (min n (inc s))))))]
        (mapcat #(go (dec c) (- s %) (list %)) (range m n))))))

This version returns the tuples as lists so as to preserve the expected ordering of results while maintaining code structure which is natural given this approach. You can convert them to vectors with a map vec pass.

For small values of the arguments, this will actually be slower than sum-c, but for larger values, it is much faster:

user> (time (last (sum-c-opt 3 500 500)))
"Elapsed time: 88.110716 msecs"
(168 167 165)
user> (time (last (sum-c 3 500 500)))
"Elapsed time: 13792.312323 msecs"
[168 167 165]

And just for added assurance that it does the same thing (beyond inductively proving correctness in both cases):

; NB. this illustrates Clojure's notion of equality as applied
;     to vectors and lists
user> (= (sum-c 3 100 100) (sum-c-opt 3 100 100))
true
user> (= (sum-c 4 50 50) (sum-c-opt 4 50 50))
true

Answer 2

for is a macro so it's hard to extend your nice idiomatic answer to cover the general case. Fortunately clojure.math.combinatorics provides the cartesian-product function that will produce all the combinations of the sets of numbers. Which reduces the problem to filter the combinations:

(ns hello.core
  (:require [clojure.math.combinatorics :as combo]))

(defn sum-three [n s i]
  (filter #(= s (reduce + %))
          (apply combo/cartesian-product (repeat i (range 1 (inc n)))))) 

hello.core> (sum-three 7 10 3)
((1 2 7) (1 3 6) (1 4 5) (1 5 4) (1 6 3) (1 7 2) (2 1 7) 
 (2 2 6) (2 3 5) (2 4 4) (2 5 3) (2 6 2) (2 7 1) (3 1 6) 
 (3 2 5) (3 3 4) (3 4 3) (3 5 2) (3 6 1) (4 1 5) (4 2 4) 
 (4 3 3) (4 4 2) (4 5 1) (5 1 4) (5 2 3) (5 3 2) (5 4 1) 
 (6 1 3) (6 2 2) (6 3 1) (7 1 2) (7 2 1))

assuming that order matters in the answers that is

Answer 3

For making your existing code parameterized you can use reduce.This code shows a pattern that can be used where you want to paramterize the number of cases of a for macro usage.

Your code without using for macro (using only functions) would be:

(defn sum-three [n s]
  (mapcat (fn [i]
            (mapcat (fn [j]
                      (filter (fn [[i j k]]
                                (and (= s (+ i j k))
                                     (< 1 k j i n)))
                              (map (fn [k] [i j k]) (range n))))
                    (range n)))
          (range n)))

The pattern is visible, there is inner most map which is covered by outer mapcat and so on and you want to paramterize the nesting level, hence:

(defn sum-c [c n s]
  ((reduce (fn [s _]
             (fn [& i] (mapcat #(apply s (concat i [%])) (range n))))
           (fn [& i] (filter #(and (= s (apply + %))
                                  (apply < 1 (reverse %)))
                            (map #(concat i [%]) (range n))))
           (range (dec c)))))