terms.lisp

(defun find-terms (num-terms max-size
                   &optional (desired-sum 0)
                   &aux (iterations 0))
  "Returns a list of terms in the range -max-size ... +max-size,
inclusive, that sum to desired-sum.

Has strange properties. Likelier to blow the stack as max-size
increases. Seems to spend most time backtracking on the last few
terms.

This feels like a glorified brute-force approach, and I think there
has to be a cleaner, closed-form way to generate similar
sequences. What would young Gauss do?"
  (labels ((rand-term ()
             (- (+ desired-sum max-size)
                (random (1+ (* 2 max-size)))))
           (find* (terms len running-sum)
             (incf iterations)
             (cond ((and (= len num-terms)
                         (= desired-sum running-sum))
                    terms)
                   ((> (abs running-sum)
                       (* max-size (- num-terms len)))
                    (find* (rest terms)
                           (1- len)
                           (- running-sum (first terms))))
                   (t (let ((next-term (rand-term)))
                        (find* (cons next-term terms)
                               (1+ len)
                               (+ running-sum next-term)))))))
    (values (find* '() 0 0) iterations)))

;;CL-USER> (find-terms 10 5)
;;(0 5 5 0 -2 -5 -4 1 4 -4)
;;29