Random integer numbers with fixed sum

user_13415477 0
Viewed 378

I'm trying to create a function that returns an array of random integer numbers whose sum is fixed.

Here is my code:

function arraySum(a) {
  return a.reduce((a, b) => a + b, 0)
}

function getRandomIntInclusive(min, max) {
  const minCeil = Math.ceil(min)
  const maxFloor = Math.floor(max)
  return Math.floor(Math.random() * (maxFloor - minCeil + 1)) + minCeil
}

function randomNumbersWithFixedSum(quantity, sum) {
  const randoms = [...Array(quantity - 1).keys()].map(q => getRandomIntInclusive(0, sum/quantity))
  const last = sum - arraySum(randoms)
  return [...randoms, last]
}

console.log(randomNumbersWithFixedSum(1, 100))
console.log(randomNumbersWithFixedSum(2, 100))
console.log(randomNumbersWithFixedSum(3, 100))
console.log(randomNumbersWithFixedSum(4, 100))
console.log(randomNumbersWithFixedSum(5, 100))

It works but it's not exactly what I want. I would like that each number is random in the range [0, sum]. In the randomNumbersWithFixedSum function I forced that the first (quantity-1) numbers are in [0, sum/quantity], but I don't like.

How can I create a really random numbers in [0, sum] whose sum is sum?

javascript
3 Answers

This is a prime example where a recursive function can simplify the problem. Each execution only calculates one random number and then calls itself with updated arguments. See the comments for a description.

function getRandomNumberBetweenIncluding(min, max) {
    return Math.floor(Math.random() * (max - min + 1)) + min;
}

function randomNumbersWithFixedSum(quantity, sum) {
    // only a single number required; return the passed sum.
    if (quantity === 1) {
        return [sum];
    }

    // Create one random number and return an array containing that number
    // as first item. Then use the spread operator and recursively execute
    // the function again with a decremented quantity and the updated  
    // maximum possible sum.
    const randomNum = getRandomNumberBetweenIncluding(0, sum);
    return [
        randomNum,
        ...randomNumbersWithFixedSum(quantity - 1, sum - randomNum),
    ];
}

console.log(randomNumbersWithFixedSum(1, 100));
console.log(randomNumbersWithFixedSum(2, 100));
console.log(randomNumbersWithFixedSum(3, 100));
console.log(randomNumbersWithFixedSum(4, 100));
console.log(randomNumbersWithFixedSum(5, 100));

user_9061130

You could take only the rest of the sum for the max random number and shuffle the array later to omit large values only at the top of the array.

function shuffle(array) {
    let i = array.length;
    while (--i) {
        let j = Math.floor(Math.random() * (i + 1)),
            temp = array[j];
        array[j] = array[i];
        array[i] = temp;
    }
    return array;
}

function getRandomIntInclusive(min, max) {
    const minCeil = Math.ceil(min)
    const maxFloor = Math.floor(max)
    return Math.floor(Math.random() * (maxFloor - minCeil + 1)) + minCeil
}

function randomNumbersWithFixedSum(length, sum) {
    length--;
    const randoms = Array.from({ length }, q => {
        const r = getRandomIntInclusive(0, sum)
        sum -= r;
        return r;
    });
    return shuffle([...randoms, sum]);
}

console.log(randomNumbersWithFixedSum(5, 100))
console.log(randomNumbersWithFixedSum(4, 100))
console.log(randomNumbersWithFixedSum(3, 100))
console.log(randomNumbersWithFixedSum(2, 100))
console.log(randomNumbersWithFixedSum(1, 100))
.as-console-wrapper { max-height: 100% !important; top: 0; }

user_14476750

What about the next solution:

  1. At the first iteration, we try to get a random number between 0 and max - say we retrieve N.
  2. At the second iteration - the max possible value cannot be greater than max - N (otherwise the sum will be greater than max).
  3. Continue for quantity - 1 steps.
  4. At the last step we have to use what is left until the max

function getRandomIntInclusive(min, max) {
  const minCeil = Math.ceil(min)
  const maxFloor = Math.floor(max)
  return Math.floor(Math.random() * (maxFloor - minCeil + 1)) + minCeil
}

function randomNumbersWithFixedSum(quantity, sum) {
  const result = [];
  let total = 0;
  
  for (let i = 0; i < quantity - 1; i++) {
    let max = sum - total;
    let num = getRandomIntInclusive(0, max);
    result.push(num);
    total += num;
  }
  result.push(sum - total);
  
  return result;
}

console.log(randomNumbersWithFixedSum(1, 100))
console.log(randomNumbersWithFixedSum(2, 100))
console.log(randomNumbersWithFixedSum(3, 100))
console.log(randomNumbersWithFixedSum(4, 100))
console.log(randomNumbersWithFixedSum(5, 100))

user_6179500
Related