2018-11-23

split an integer into summands

here is an example algorithm for generating numbers whose sum is a specific integer. asking for the summands of an integer is a question with multiple solutions and in this case a random number generator is used to give one possible solution.

to create a function that splits an integer int into count integers equal or greater than minimum whose sum is int, with the following signature:

integer_summands :: integer:int integer:count integer:minimum -> (integer ...)

and the following domain:

any_integer = int
0 <= count
(count * minimum) < int
  • get count random numbers of the range minimum to int
  • scale numbers by int divided by sum-of-numbers so to preserve relative differences
  • add either 1 or -1 to every number at random indices until the sum is int

properties

  • different random distributions can be used to change the result distribution
  • depending on the random number generator and distribution, numbers near int may be less likely the higher count is. in tests with uniform distribution and int 50, count 4, minimum 2, the maximum possible value 44 occurred about 1:30000 applications

example implementation in scheme

(define (map-integers count f)
  "integer {integer -> any} -> list
   map over integers from 0 to count - 1"
  (let loop ((n 0)) (if (= n count) (list) (cons (f n) (loop (+ 1 n))))))

(define (integer-summands int count minimum)
  (if (> (* count minimum) int) (list)
    (let*
      ( (numbers (map-integers count (l (a) (+ minimum (random (- int minimum))))))
        (numbers-sum (apply + numbers))
        (scale (if (= 0 numbers-sum) 1 (/ int numbers-sum)))
        (numbers (map (l (a) (round (max minimum (* scale a)))) numbers))
        (deviation (- int (apply + numbers))))
      (if (= 0 deviation) numbers
        (let*
          ( (adjust (if (> 0 deviation) -1 1))
            (numbers (list->vector numbers)))
          (let loop
            ( (deviation (abs deviation))
              (index (random count)))
            (let ((adjusted (+ adjust (vector-ref numbers index))))
              (if (> minimum adjusted) (loop deviation (random count))
                (begin
                  (vector-set! numbers index adjusted)
                  (if (= 1 deviation) (vector->list numbers)
                    (loop (- deviation 1) (random count))))))))))))

example usage

(integer-summands 50 4 2)

example results

(19 17 3 11)
(9 16 12 13)
(2 20 4 24)
(32 3 5 10)