Algorithms – Generating N Random Numbers Between A and B Summing to X

algorithmsc

This problem seemed like something which should be solvable with but a few lines of code.

Unfortunately, once I actually started to write the thing, I've realized it's not as simple as it sounds.

What I need is a set of X random numbers, each of which is between A and B and they all add up to X. The exact variables for the problem I'm facing seem to be even simpler: I need 5 numbers, between -1 and 1 (note: these are rational (floating point) numbers), which add up to 1.

My initial "few lines of code, should be easy" approach was to randomize 4 numbers between -1 and 1 (which is simple enough), and then make the last one 1-(sum of previous numbers). This quickly proved wrong, as the last number could just as well be larger than 1 or smaller than -1.

What would be the best way to approach this problem?

PS. Just for reference: I'm using C#, but I don't think it matters. I'm actually having trouble creating a good enough solution for the problem in my head.

I also wanted to provide my current solution to the problem, but do remember that it's quite imperfect and it was created as a quick fix to the initial problem!

  • Generate 4 random numbers between -1 and 1
  • Create a "final" number X=SUM(previousNumbers)
  • If the final number is >1 or <-1, then:
    • Get the "amount" over 1 / under -1 and make the last number a 1 / -1
    • Find another number which can accept this amount and still inside the brackets
    • If no number can take the amount (it's too large / too small) then divide the amount in half and try again for each half
  • Randomize the order of the generated numbers and return them

This works in the sense that this algorithm generates 5 numbers which are between -1 and 1 and their sum is 1. However the downside is that quite often one of the generated numbers is a 1 (or -1), which doesn't feel very random.

Best Answer

As said before, this question actually doesn't have an answer: The restrictions imposed on the numbers make the randomness questionable at best.

However, you could come up with a procedure that returns a list of numbers like that:

Let's say we have picked the first two numbers randomly as -0.8 and -0.7. Now the requirement is to come up with 3 'random' numbers that sum up to 2.5 and are all in the range [-1,1]. This problem is very similar to the starting problem, only the dimensions have changed. Now, however, if we take a random number in the range [-1,1] we might end up with no solution. We can restrict our range to make sure that solutions still exist: The sum of the last 2 numbers will be within the range [-2,2]. This means we need to pick a number in the range [0.5,1] to make sure we can reach a total of 2.5.

The section above describes one step in the process.

In general: Determine the range for the next number by applying the range of the rest of the numbers to the required sum. Pseudo-code:

function randomNumbers (number, range, sum) {
  restRange = range * (number - 1)
  myRange = intersection ([sum - restRange.upper, sum - restRange.lower], range)

  myNumber = random(myRange)

  rest = randomNumbers (number-1, range, sum - myNumber)

  return [myNumber, rest]
}

So for the case described above

randomNumbers (3, [-1,1], 2.5)
  restRange = [-1,1] * (3-1) = [-2,2]
  myRange = intersection ([2.5-2,2.5-(-2)], [-1,1]) = intersection ([0.5,4.5],[-1,1]) = [0.5,1]

A quick-and-dirty implementation in Java:

public class TestRandomNumberList
{

    @Test
    public void test()
    {
        double[] numbers = new double[5];
        randomNumbers(numbers, 0, -1, 1, 1);
        assertEquals(sum(numbers), 1.0, 0.00001);
        for (double d : numbers)
        {
            assertTrue(d >= -1 );
            assertTrue(d <= 1);
        }
    }

    private void randomNumbers(double[] numbers, int index, double lowerBound, double upperBound, double sum)
    {
        int next = index + 1;
        if (next == numbers.length)
        {
            numbers[index] = sum;
        }
        else
        {
            int rest = numbers.length - next;  

            double restLowerBound = lowerBound * rest;
            double restUpperBound = upperBound * rest;

            double myLowerBound = Math.max(lowerBound, sum - restUpperBound);
            double myUpperBound = Math.min(upperBound, sum - restLowerBound);

            numbers[index] = random(myLowerBound, myUpperBound);
            randomNumbers(numbers, next, myLowerBound, myUpperBound, sum - numbers[index]);
        }
    }

    private double random(double myLowerBound, double myUpperBound)
    {
        double random = Math.random();
        return myLowerBound + random * (myUpperBound - myLowerBound);
    }

    private double sum(double[] numbers)
    {
        double result = 0;
        for (double num : numbers)
        {
            result += num;
        }
        return result;
    }

}
Related Topic