Generate N random numbers in given ranges that sum up to a given sum

Question

first time here at Stackoverflow. I hope someone can help me with my search of an algorithm.

I need to generate N random numbers in given Ranges that sum up to a given sum!

For example: Generatare 3 Numbers that sum up to 11.

Ranges:

1. Value between 1 and 3.
2. Value between 5 and 8.
3. value between 3 and 7.

The Generated numbers for this examle could be: 2, 5, 4.

I already searched alot and couldnt find the solution i need.

It is possible to generate like N Numbers of a constant sum unsing modulo like this: generate random numbers of which the sum is constant But i couldnt get that done with ranges.

Or by generating N random values, sum them up and then divide the constant sum by the random sum and afterwards multiplying each random number with that quotient as proposed here.

Main Problem, why i cant adopt those solution is that every of my random values has different ranges and i need the values to be uniformly distributed withing the ranges (no frequency occurances at min/max for example, which happens if i cut off the values which are less/greater than min/max).

I also thought of an soultion, taking a random number (in that Example, Value 1,2 or 3), generate the value within the range (either between min/max or min and the rest of the sum, depending on which is smaller), substracting that number of my given sum, and keep that going until everything is distributed. But that would be horrible inefficiant. I could really use a way where the runtime of the algorithm is fixed.

I'm trying to get that running in Java. But that Info is not that importend, except if someone already has a solution ready. All i need is a description or and idea of an algorithm.

Answer 1

First, note that the problem is equivalent to:

Generate k numbers that sums to a number y, such that x_1, ..., x_k - each has a limit.

The second can be achieved by simply reducing the lower bound from the number - so in your example, it is equivalent to:

Generate 3 numbers such that x1 <= 2; x2 <= 3; x3 <= 4; x1+x2+x3 = 2

Note that the 2nd problem can be solved in various ways, one of them is:

Generate a list with h_i repeats per element - where h_i is the limit for element i - shuffle the list, and pick the first elements.

In your example, the list is:[x1,x1,x2,x2,x2,x3,x3,x3,x3] - shuffle it and choose first two elements.

(*) Note that shuffling the list can be done using fisher-yates algorithm. (you can abort the algorithm in the middle after you passed the desired limit).