current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.
up vote 6 down vote favorite

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.

share|improve this question
6  
The numbers can't be simultaneously completely random and guaranteed to add up to 1. You could pick 5 random numbers between -1 and 1, and then normalize their sum to 1 after the fact. That is, divide each of the 5 random numbers by their sum before returning them. –  Charles E. Grant Aug 24 at 16:15
    
@CharlesE.Grant Wouldn't doing this cause the numbers to never be 1 or -1? Also, I'm not sure I follow... I just tried this in Excel: Generated: -0.57; 0.28; 0.41; -0.5; 0.53; SUM=0.15. After dividing each I get: -3.8; 1.86; 2.73; -3.33; 3.53. While THESE numbers DO sum up to 1, they aren't within the required boundaries. –  Shaamaan Aug 24 at 20:24
3  
The trouble is that your problem as stated simply doesn't have a solution! There are an infinite number of choices for the first three numbers where no choice for the second two numbers will give a sum of 1 (-0.9, -0.8, -0.7 for example). The headache is your requirement that each of the numbers comes from the same range, but that they have a fixed sum. Because of the fixed sum, as soon as you pick a number you are changing the feasible range of the following numbers, so you have contradictory requirements. –  Charles E. Grant Aug 24 at 23:31
    
Choose 5 numbers uniformly distributed across the interval [-1,+1] and (on average) the sum will be 0. To achieve the sum of 1 you must permit a non-uniform distribution. What distribution will it be? –  david.pfx 2 days ago
    
Please clarify "decimal number". Decimal means a base-10 representation, just as hexadecimal means base 16. Whether numbers add up to 1 depends on their value, not their representation. –  MSalters 2 days ago

6 Answers 6

up vote 2 down vote accepted

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;
    }

}
share|improve this answer
    
A friend of mine suggested something similar, when I asked him the question. This seems fairly decent and I'll try it out! :) –  Shaamaan 2 days ago
up vote 2 down vote

Simple, as long as you know how many.

  1. You need N numbers called V1 to Vn. The required sum is S.
  2. Generate N random numbers (in any convenient range). They are R1 to Rn.
  3. Calculate their sum as SR.
  4. Scale each number so Vn = Rn * S / SR.

You may produce a tiny rounding error, but I doubt this will be a problem.

If the number N is supposed to be random, then choose that first.

My apologies, I missed the requirement for the numbers to be between A and B. The algorithm is exactly the same. Pick N random numbers, then scale them based on A, B, actual sum and required sum. I leave the rest as an implementation detail.

share|improve this answer
    
Aren't you ignoring the requirement that the N numbers need to be between A and B? From my understanding, your algorithm only produces N random numbers that add up to X and have some arbitrary range that is determined by the range used in step 2. It seems you should add some detail to step 2, because "any convenient range" won't exactly work here. Using the range A to B for step 2 wouldn't work either so I doubt it is all that trivial. –  Shashank Gupta 2 days ago
1  
This is generally not true. The scaling might take numbers out of the range. Consider the case as in the question with the original random numbers [1,1,-1,-1,0.5]. Their sum is 0.5 and to come to a total of 1, we multiply by 2, taking the first 4 numbers to values outside the original range. –  Maarten Winkels 2 days ago
    
See edit. The principle is the same, but the details of the scaling require some thought. –  david.pfx 2 days ago
    
The method works and is highly general, but I see now that the problem cannot be solved for a uniform distribution. OP to comment? –  david.pfx 2 days ago
    
If you're looking for my input, I do believe you chugged a vital part of the answer to "implementation detail". :| Otherwise I now see that there is no "truly random" solution to this problem, and I'll be happy to take what I can get. –  Shaamaan 2 days ago
up vote 0 down vote

You can start with any 5 random numbers in the range, but then you just need to pay attention to which are negative and which are positive.

Case (A) : All 5 numbers are positive.

Here you can just divide by their sum. The sum is guaranteed to be greater than each individual number, since each number N is positive. Then you have 

0 < N < 1

for each individual number N, and you have the normalized sum equal to 1.

Case (B) : Positives and negatives.

First normalize the negatives so that their sum is 

-1 < (Sum of normalized negatives) < 0

At this point we are sure that each negative number is still within the range

-1 < N_negative < 0.

for each individual negative number N_negative.

Next normalize the positives so that 

1 - (Sum of normalized positives) = (Sum of normalized negatives)

Now we might have got into trouble taking one or more of the positive numbers outside of the range. Check if that happens. If not, then we are done. If so, then renormalize the positive numbers so that the maximum individual value is 1. We know that the sum of renormalized positives will be less than the sum of the first positive normalization, but also the renormalized sum will be greater than 1. Therefore we can renormalize the negatives so that 

1 - (Sum of *re*normalized positives) = (Sum of *re*normalized negatives)

And now we are definitely done with case B.

Case (C) : All 5 numbers are negative.

This has no solution.

share|improve this answer
up vote 0 down vote

One option to solve this problem is to build a search tree. The goal state will be the sum of all nodes along your current path equal X. Each node is a different value between the range, so the number of nodes at each level will be abs(A) + abs (B). Explore all the paths and get all the possible solutions. Then choose one at random from the list of solutions.

The search space will become too large to calculate when N and abs(A) + abs (B) are large. You can limit the search space by creating rules. A simple rule here would be that if the path contains the same values, but in a different order, then they are considered the same. That would eliminate a lot of paths on the search tree. You can think up a lot more to limit the search space, but I will leave that exercise to you.

Note: This solution is overkill, but it's a fun exercise.

share|improve this answer
up vote 0 down vote

I'd start out by simplifying the problem. If you have N numbers from [A,B], they will add up to a value between N*A and N*B. Just subtract A from each number and N*A from the target X.

So, without loss of generality we can look for N numbers between [0, B'] which add up to X'. Again, this can be simplified by dividing X' by B'.

The resulting problem is looking for N numbers in [0,1] which add up to X" = (X-A)/(B-A).

What's the distribution of these random numbers? The requirement that they add up to X" means that they can't be independent distributions. I'll assume that we want the same distribution for all N numbers. Otherwise, it's trivial. If we know all distributions are the same, we do know that their mean has to be X"/N. This is not necessarily 1/2, so we have to come up with a possibly asymmetric distribution over [0,1] - a symmetric distribution does have mean 0,5 since p(x)==p(1-x). Yet all numbers should be possible if X"/N is not 0 or 1.

At this point, you can freely choose any parametrized distribution which allows for means in (0,1). An exponential distribution should work fine.

Finally, once you've drawn one number A(0) from this distribution, you should recurse and calculate a new distribution for the next number as you now need to find N-1 numbers which add up to X"-A(0). And of course for the last number you have no choice left.

share|improve this answer
up vote 0 down vote

To get a Gaussian distribution, roll all numbers independently. Apply your predicate (e.g. Sum of numbers lies within [-1, 1]). If it fails, re-roll all numbers. When your predicate succeeds, you are done.

This will, on average, terminate on some fixed iteration (if the predicate is ever satisfiable, and your RNG is not broken). Be sure to use an epsilon comparison for testing your floats.

share|improve this answer
    
Considering that on average half the numbers will be negative and cause you to diverge from the sum, I believe this is not an optimal solution. While it may generate valid solutions, my gut feeling without doing the math is that they will not be uniformly distributed. –  Snowman yesterday
    
Whoops, I meant Gaussian. –  Thomas Eding yesterday

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.