2020-04-09

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 find one possible solution. the relative distribution of summands is information that is lost in a sum

algorithm

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:

int = integer
count >= 0
int > (count * minimum)
  • get count random numbers in the range minimum to int
  • scale each number by int divided by sum-of-numbers to adjust the sum while preserving relative differences
  • add 1 or -1 to every number at random indices until the sum equals int

properties

  • the result distribution will correspond to the random distribution
  • depending on the random number generator and distribution, numbers near int may be less likely to occur the higher count is. in tests with uniform distribution and int 50, count 4, minimum 2, the maximum possible value 44 occurred only in 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)