3

Program that gets a user input N and finds 5 random integers following the below 2 constraints:

(a) the minimum and maximum value for each random value:

(i)   25 ≤ random_val_1 ≤ 30

(ii)  25 ≤ random_val_2 ≤ 30

(iii) 17 ≤ random_val_3 ≤ 20

(iv)  5 ≤ random_val_4 ≤ 10

(v)   8 ≤ random_val_5 ≤ 10

(b) sum(random_val_1, random_val_2, random_val_3, random_val_4, random_val_5) should be equals N

The output should be in the following form:

[ <int> random_val_1, <int> random_val_2, <int> random_val_3, <int> random_val_4, <int> random_val_5 ]

I was able to generate random values and only pass the residue of the given input N to the remaining random values to satisfy constraint (b) but not (a)

StackUnderflow
  • 51
  • 5
  • Awesome problem, this reminds me of the classic "Given probabilities {p_1, ..., p_n}, Choose k elements among {1, ..., n} such that each element i has probability p_i of being chosen." – Stef Jan 16 '23 at 16:03
  • *"I was able to generate random values and only pass the residue of the given input N to the remaining random values to satisfy constraint (b)"* Sooooo does that mean you successfully solved the problem? – Stef Jan 16 '23 at 16:14
  • `25 <= random_val_4 <= 10` - seems like impossible constraint for `random_val_4`. No integer value exists with such constraints. – ks1322 Jan 16 '23 at 16:16
  • @Stef I was not able to get the answer, so for example if I randomly generate the fullest value for the random_val 1,2,3,4 then random_val 5 wont have any value to fulfill constraint (a) – StackUnderflow Jan 16 '23 at 16:20
  • @ks1322 i'm sorry, I've made the changes – StackUnderflow Jan 16 '23 at 16:23
  • 2
    What do you call random ? Is there a precise probability law that you wish to follow ? Or do you just wish to get unpredictable results (but potentially with sme results more likely to happen) ? – Joseph Budin Jan 16 '23 at 16:29
  • Perhaps you ca get inspiration from this question: [Uniformly selecting a distribution of items into bins?](https://stackoverflow.com/questions/43566121/uniformly-selecting-a-distribution-of-items-into-bins) This question has all bins the same size instead of different sizes, but is otherwise similar. – Stef Jan 16 '23 at 16:37
  • @josephBudin just a naive way to solve it, no precision is needed – StackUnderflow Jan 16 '23 at 16:37
  • 1
    @StackUnderflow Assuming you don't care about the exact probability distribution, then one simple naive way is to iterate by adding 1 to a random bin until you've reached N (starting from all bins having their minimum value). Alternatively you can start with all bins having their maximum value, and iterate by removing 1 from a random bin until you've reached N. – Stef Jan 16 '23 at 16:39
  • @Stef yes, I get it thanks! – StackUnderflow Jan 16 '23 at 16:41
  • @StackUnderflow Alternatively, start with random values for every bin, taken uniformly at random within their bounds. Then compute the sum. If it's higher than N, then loop by removing 1 from a random bin until you reach N; if it's lower than N, then loop by adding 1 to a random bin until you reach N. – Stef Jan 16 '23 at 16:42
  • Perhaps this question has better answers: [How to create a list of random integer vector whose sum is x?](https://stackoverflow.com/a/11380564/3080723) – Stef Jan 16 '23 at 16:45

2 Answers2

3

We can see that for the given values, generating all possible solutions and randomly picking one won't take much time, as there are atmost (30 - 25 + 1) * (30 - 25 + 1) * (20 - 17 + 1) * (10 - 5 + 1) * (10 - 8 + 1) = 2592 possibilities.

For generating the numbers, we can observe that N cannot be less than the sum of all minimum constraint at each index. We can use this fact to recursively reduce the search space and generate the numbers.

Here's an implementation in C++.

Note that we can move the "random generation part" for picking the value at each index, instead of randomly picking one from all possible solutions, as in the former case, on average the runtime would be faster than the latter method (depending on the random generation method used).

sharpnife
  • 198
  • 12
0

So N is between 80 and 100. If N is 80 there is nothing to sample, same if N=100.

If N is set to something in the range [81...99], then find mean values M1, M2, M3, M4, and M5 still within the constrain (a) and summed to N.

Then find probabilities

p1 = M1/N, p2=M2/N, ...

Then use your favorite Multinomial distribution sampling routine with probabilities p1, p2, ...p5, and N as sum, and reject any sample that violates (a).

(b) would be satisfied automatically cause of distribution properties

Severin Pappadeux
  • 18,636
  • 3
  • 38
  • 64