2024-12-04

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 n into count integers equal to or greater than min whose sum is n, with the following signature:

integer_summands :: integer:n integer:count integer:min -> (integer ...)

and the following domain:

n = integer
count >= 0
n >= (count * min)
  • subtract count * min from n to get the remaining total
  • get count - 1 random numbers in the range 0 to the remaining total
  • sort these random numbers along with the endpoints 0 and the remaining total
  • calculate the differences between consecutive numbers and add min to each to ensure the minimum value constraint

properties

  • the result distribution will correspond to the random distribution
  • depending on the random number generator and distribution, numbers near n may be less likely to occur the higher count is. in tests with uniform distribution and n = 50, count = 4, min = 2, the maximum possible value 44 occurred only in about 1:30000 applications.

example implementation in coffeescript

integer_summands = (n, count, min) ->
  t = n - count * min
  return [] if t < 0
  s = [0, t].concat((Math.floor(Math.random() * (t + 1)) for _ in [1...count]))
  s.sort (a, b) -> a - b
  s[i + 1] - s[i] + min for i in [0...count]

example usage

integer_summands 50, 4, 2

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

[12, 2, 28, 8]
[20, 5, 12, 13]
[14, 16, 16, 4]
[11, 21, 7, 11]
[2, 13, 23, 12]

without repetition

integer_summands_unique = (n, count, min) ->
  s = count * min + (count * (count - 1)) / 2
  return [] if n < s
  t = n - s
  a = (Math.floor(x * t) for x in ([Math.random() for _ in [1...count-1]].sort()))
  a = (a[i] - (a[i-1] || 0) for i in [0...a.length]).concat [t - (a[a.length-1] || 0)]
  a = a.sort () -> Math.random() - 0.5
  (min + i + a[i] for i in [0...count]).sort (a, b) -> a - b
  • calculate the required minimum sum
  • return empty array if n is less than the required minimum sum
  • t: calculate the extra amount to distribute
  • a: generate sorted random break points and convert to integer partition
  • a: calculate the differences between break points and add the last partition
  • a: shuffle the extras randomly
  • create the summands by adding min and index to each extra and shuffle them