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

this exercise 2.41 in sicp have wrote naive version myself:

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

the question is: considered idiomatic in clojure? , how can optimize piece of code? since takes forever compute(sum-three 500 500)

also, how can have function take argument specify number of integer compute sum? instead of sum of three, should handle more general case sum of two, sum of 4 or sum of 5 etc.

i suppose cannot achieved using for loop? not sure how add j k binding dynamically.

(update: optimized version sum-c-opt @ bottom.)

i'd idiomatic, if not fastest way while staying idiomatic. well, perhaps using == in place of = when inputs known numbers more idiomatic (nb. these not entirely equivalent on numbers; doesn't matter here though.)

as first optimization pass, start ranges higher , replace = number-specific ==:

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

(changed ordering of bindings since want smallest number last.)

as making number of integers parameter, here's 1 approach:

(defn sum-c [c n s]   (letfn [(go [c n s b]             (if (zero? c)             [[]]             (for [i  (range b n)                   (go (dec c) n (- s i) (inc i))                   :when (== s (apply + is))]               (conj i))))]     (go c n s 0)))  ;; 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 exercise use it, math.combinatorics provides combinations function tailor-made solve problem:

(require '[clojure.math.combinatorics :as c])  (c/combinations (range 10) 3) ;=> combinations of 3 distinct numbers less 10; ;   returned lists, in fact distinct ;   sets, no (0 1 2) / (2 1 0) "duplicates modulo ordering"; ;   happens individual lists maintain ;   relative ordering of elements input, although docs ;   don't guarantee 

filter output appropriately.

a further update: thinking through way sum-c above works gives 1 further optimization idea. point of inner go function inside sum-c produce seq of tuples summing target value (its initial target minus value of i @ current iteration in for comprehension); yet still validate sums of tuples returned recursive calls go if unsure whether job.

instead, can make sure tuples produced 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 tuples lists preserve expected ordering of results while maintaining code structure natural given approach. can convert them vectors map vec pass.

for small values of arguments, slower sum-c, larger values, 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 added assurance same thing (beyond inductively proving correctness in both cases):

; nb. illustrates clojure's notion of equality applied ;     vectors , 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