2023-02-27

# 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)))
(if (> minimum adjusted) (loop deviation (random count))
(begin
`(integer-summands 50 4 2)`
```(19 17 3 11)