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.

Kerk

Impossible. If they meet your requirement they are not truly random. – Suisse

@HotLicks - I disagree, they could be random (leaving aside we cannot generate random numbers) - but with lower degree of freedom on the number of randomizations needed. I find this claim identical to "cannot generate a random number in range [0,10] - because the restriction makes it impossible for true randomization". – Bourgeoisie

@Bourgeoisie - But after you've picked the first two numbers, the 3rd number isn't random at all. – Suisse

So, you have 2 random numbers - still random. – Bourgeoisie

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).

Bourgeoisie

Exactly what i needed, thanks. Still have to think about the complexity with a large K and larger ranges (like hundreds,e.g 50-150) and memory consumption of the list – Kerk

you don't necessarily have to create the list. if you need just a couple of samples, you can use a virtual list, without shuffle. randomly select the position, based on that, you can get the element (count down, skip marked elements, etc..) – Adabelle

Took me a few years to understand how this works, but now that I do, I appreciate how elegant a solution this is – Carbolize

Answer 2

Add up the minimum values. In this case 1 + 5 + 3 = 9

11 - 9 = 2, so you have to distribute 2 between the three numbers (eg: +2,+0,+0 or +0,+1,+1).

I leave the rest for you, it's relatively easy to create a uniform distribution after this transformation.

Adabelle

This is a way to do it, but not the way i wanted it. Or to be more specific, the problem itself is the distribution of the points here. But sorry, its my fault (bad example or bad problem description). In another Example with other ranges: 1. 1-3 2. 2-20 3. 1-3 and a sum of, lets say 15, value 1 and 2 would in most cases reach its maximum. This is not what i wanted. amits solution is what was in my mind. The points need to be distributioned by a weight, depending on how big the range is – Kerk

@Kerk did u get your answer? how did you solve it.. Please share even i want to write something like this – Itis

Answer 3

This problem is equivalent to randomly distributing an excess of 2 over the minimum of 9 on 3 positions.

So you start with the minima (1/5/3) and then cycle 2 times, generating a (pseudo-)random value of [0-2] (3 positions) and increment the indexed value.

e.g.

• Start 1/5/3
• 1st random=1 ... increment index 1 ... 1/6/3
• 2nd random=0 ... increment index 0 ... 2/6/3

2+6+3=11

Edit

Reading this a second time, I understand, this is exactly what @KarolyHorvath mentioned.

Lunulate

Answer 4

Amit's answer is great, but I found the description slightly confusing. As a simple example, consider the case where you want three random numbers between zero and five that add up to ten. Make a list with the letters a, b and c each repeated five times. Then make a random permutation of the list and look only at the first ten elements. a, b and c occur zero to five times each, out of a total of ten letters.

Ellsworthellwood