Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Array of random numbers with sum in given range?

In C, how do I get an array of n numbers (each 0x00-0xFF in my case), of which the sum is within a given range 0..k?

The almost duplicate C++ multiple random numbers adding up to equal a certain number targets a specific sum, but in my case the sum can be anything between 0..k.

like image 413
Moeder Avatar asked Jun 10 '15 08:06

Moeder


2 Answers

You need to specify what is the desired distribution of the random numbers.

If there are no further requirements, I would suggest one of the following:


(1)

  • pick random number a[1] in interval 0 .. k
  • pick random number a[2] in interval 0 .. k-a[1]
  • pick random number a[3] in interval 0 .. k-a[1]-a[2]
  • ...
  • pick random number a[n] in interval 0 .. k-a[1]-a[2]-...-a[n-1]

If you have upper limit m on the range of the random number, use min(k-a[1]-... m) as upper bound of the interval.

Disadvantages: you will get a lot of small numbers and just a few big ones.


(2)

  • pick n random numbers a[1], .., a[n] in interval 0 .. m, m being the upper limit
  • s = a[1]+a[2]+...+a[n]
  • multiply each a[i] by k/s (if integers are required, round down)

Disadvantages: It is unlikely to get large numbers this way. If integers are required, there will likely be a gap between the sum of numbers and k due to rounding error.


I think you get "nicer" numbers with option (2) but as stated above, it depends on the requirements.

like image 131
Blaf Avatar answered Sep 22 '22 17:09

Blaf


Assuming k is less than 255 * n one solution is to assign k / n to every element of the array, then randomly subtract a value to the array elements.

// for (int i = 0; i < n; i++) array[i] = k / n;
// for (int i = 0; i < n; i++) array[i] -= randbetween(0, array[i]);
for (int i = 0; i < n; i++) array[i] = randbetween(0, k / n);

This has an expected sum of k / 2. By tweaking the randbetween() function you can change the probability of the resulting array sum.

like image 26
pmg Avatar answered Sep 21 '22 17:09

pmg