2020-04-09

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

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`

- 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

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