Как получить одно решение уравнения u + v + x + y + z = 100 в Clojure

Question

У меня возникла проблема, заключающаяся в том, что как написать функцию clojure для получения одного решения уравнения u + v + x + y + z = 100, все переменные являются положительными целыми числами. Функция работает так, если мы запускаем (fun 100), тогда мы получаем одно решение (например, [1 10 49 3 37]), если мы снова выполним (fun 100), у нас получится другое решение (возможно, [29 46 7 12 6])

Answer 1

Этого можно достичь с помощью определения списка for. Учитывая, что у вас есть пять переменных, необходимо выполнить 10B операций, и для грубой силы требуется немного времени (по крайней мере несколько минут на ядре i7. Лучше всего искать интеллектуальный алгоритм, который скажет например, что когда x равно 98, y равно 1, а z равно 1, тогда нет необходимости в цикле через u и v, так как они должны быть равны нулю. Но вот здесь подход грубой силы:

(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])) 

Теперь у вас есть ленивый список всех решений. Будьте осторожны с этим, поскольку очень интенсивно выполнять вычисления (count solns) или (rand-nth solns) (это займет около 10 минут на современной машине), поскольку весь список будет реализован. Как только список будет реализован, вы можете легко получить действительно случайные решения с (rand-nth solns) в качестве computatio n уже сделано. Есть 4598126 решений.

Answer 2

В ответе Джоша упоминается умный алгоритм, который не тратит время на пустые тупиковые пути. Этот алгоритм достаточно прост для написания, отслеживая непогашенную сумму и только выбирая числа, не превышающие то, что осталось.

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

Он получает те же ответы, что и перебор подход, и вместо десяти минут она занимает десять секунд, чтобы найти их:

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

Answer 3

Наконец я получил ответ сам:

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

Это действительно работает и занимает менее 1 мсек, чтобы получить результат

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

Но код выглядит немного сложнее, может ли кто-нибудь показать нам более сжатое решение?