2024-10-13

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 coffeescript

map_integers = (count, f) -> (f n for n in [0...count])

integer_summands = (int, count, minimum) ->
  if count * minimum > int then []
  else
    numbers = map_integers count, (a) -> minimum + Math.floor Math.random() * (int - minimum)
    numbers_sum = numbers.reduce ((a, b) -> a + b), 0
    scale = if numbers_sum == 0 then 1 else int / numbers_sum
    numbers = numbers.map (a) -> Math.round Math.max minimum, scale * a
    deviation = int - numbers.reduce ((a, b) -> a + b), 0
    if deviation == 0 then numbers
    else
      adjust = if deviation > 0 then 1 else -1
      deviation = Math.abs deviation
      while deviation > 0
        index = Math.floor Math.random() * count
        adjusted = numbers[index] + adjust
        if adjusted >= minimum
          numbers[index] = adjusted
          deviation -= 1
      numbers

example usage

integer_summands 50, 4, 2

example results (results will vary because of the use of random)

[19, 17, 3, 11]
[9, 16, 12, 13]
[2, 20, 4, 24]
[32, 3, 5, 10]