How to get one solution of the equation u + v + x + y + z = 100 in Clojure

Question

I've faced a problem that how to write a clojure function to get one solution of the equation u + v + x + y + z = 100, all variables are positive integers. The function works like this , if we run （fun 100）then we get one solution (such as [1 10 49 3 37]), if we run （fun 100）once more, we got another solution (maybe [29 46 7 12 6])

Related: http://stackoverflow.com/questions/2640053/getting-n-random-numbers-that-the-sum-is-m — Caramiriel, Feb 14 '17 at 07:04
Possible duplicate of [Getting N random numbers that the sum is M](http://stackoverflow.com/questions/2640053/getting-n-random-numbers-that-the-sum-is-m) — M. Adeel Khalid, Feb 14 '17 at 07:06
What did you do to achieve this? Show your code/efforts here.StackOverflow is not a code writing service. If you have a problem with your code, please provide Minimal, Complete, and Verifiable example. — Shubham Verma, Feb 14 '17 at 07:13

score 4 · Answer 1 · answered Feb 14 '17 at 16:51

4

Josh's answer mentions a smart algorithm that doesn't waste time brute-forcing dead-end paths. This algorithm is quite simple to write, by tracking the outstanding sum and only choosing numbers no larger than what remains.

(defn sums-to [n total]
  (case n
    1 [[total]]
    (for [i (range (inc total))
          solution (sums-to (dec n) (- total i))]
      (cons i solution))))

It gets the same answers as the brute-force approach, and instead of ten minutes it takes ten seconds to find them:

user> (time (count (sums-to 5 100)))
"Elapsed time: 12734.779787 msecs"
4598126

answered Feb 14 '17 at 16:51

amalloy

89,153
8
140
205

deserves a +1, very nice :) – Josh Feb 14 '17 at 17:23
This most simple thing is Mindblowing – jstuartmilne Sep 06 '17 at 02:14

score 2 · Answer 2 · answered Feb 14 '17 at 16:34

This can be achieved with the for list comprehension. Given that you have five variables, there are 10B operations that must be performed, and to brute force it takes a bit of time (a few minutes at least on a core i7 machine. Your best bet is to seek a smart algorithm which will say, for example, that when x is 98, y is 1, and z is 1, then there's no use in looping through u and v, as they must be zero. But, here is the brute force approach:

(def solns (for [x (range 101)
                 y (range 101)
                 z (range 101)
                 u (range 101)
                 v (range 101)
                 :when (= 100 (+ x y z u v))]
             [x y z u v]))

Now, you have a lazy list of all solutions. Be careful with this, as it's very computationally intensive to perform a (count solns) or (rand-nth solns) (it will take maybe 10 minutes on a modern machine), as the whole list will be realized. Once the list is realized though, you can easily get truly random solutions with (rand-nth solns) as the computation is already done. There are 4,598,126 solutions.

Pluto Qian · Answer 3 · 2017-02-16T11:31:01.510

Finally I got the answer myself:

(defn fun [total-sum]
  (let [init-part-list (repeat 4 1)
        sum (atom (- total-sum (apply + init-part-list)))
        part-list (map #(let [r (rand-int @sum)]
                           (reset! sum (- @sum r))
                           (+ % r))
                       init-part-list)]
    (cons (- total-sum (apply + part-list)) part-list)))

It really works and takes less than 1 msecs to get the result

=> (time (fun 100))
"Elapsed time: 0.070562 msecs"

But the code look a little bit complicated, can anyone show us a more concise solution?

How to get one solution of the equation u + v + x + y + z = 100 in Clojure

3 Answers3