3

I saw tons of answers to this question on the web but, can you believe me? I still don't get the solution of this problem. I have an array of values. The size of this array is "n". I have also the defined value "sum". What I want is to generate "n" random values in such a way that their sum is equals to "sum", preferably uniformly distributed, otherwise (for example) having the first random number equals to "sum" and the rest equals to zero is not that nice. I need two algorithms which accomplish this task. One with positive Integers and one with positive Floats. Thanks a lot in advance!

Tarta
  • 1,729
  • 1
  • 29
  • 63
  • You mean you want each possible combination of `n` values that sum up to `sum` to be chosen with uniform distribution? – Joseph Mansfield Jun 04 '14 at 16:46
  • What about the solution don't you get? (It would also help if you included the solution in your question.) – jwodder Jun 04 '14 at 16:47
  • 3
    You want _n_ values summing to _sum_, but if they're not uniformly distributed that's ... kind of ok but not ideal? Is that really your requirement? – Useless Jun 04 '14 at 16:48
  • Joseph, yes, that's what I mean, I think. The point is.. suppose sum = 10 and n = 4. Good random values would be 3,3,3,1 for example. If I have instead of that 9,1,0,0 they are not well distributed.. I hope I am more clear now since applying the concept of "uniform distribution" to values is not that easy... – Tarta Jun 04 '14 at 16:52
  • Jwodder, there are plenty of solutions. If you just type "Random values with fixed sum" you will find out what I mean :) – Tarta Jun 04 '14 at 16:55
  • Useless, unfortunately I need them uniformly distributed otherwise I know how to formulate the algorithm :) – Tarta Jun 04 '14 at 16:56
  • From a mathematical standpoint, this seems contradictory. A uniformly distributed random vector cannot be forced to have a fixed sum because you introduce dependence between the elements and therefore change the shape of the probability mass function. – nispio Jun 04 '14 at 17:05
  • So now we're going to have yet another solution for the problem. Why didn't you ask about it in a chat room instead of contributing to the mess? – Lightness Races in Orbit Jun 04 '14 at 17:10
  • pjs, no they are not :) – Tarta Jun 04 '14 at 17:26
  • 1
    @Tarta is this just your homework ? or are you running into this achieving some functionality? – nl-x Jun 04 '14 at 17:27
  • @nl-x it's a functionality of a big project (which is a homework :D ). Your solution and the one of JaBe are both really good.. but yours seems working with integer if I am not wrong. Few minutes and I will check it out. – Tarta Jun 04 '14 at 17:47
  • I think here's what you are looking for: http://coliru.stacked-crooked.com/a/dda73eeb281013a6 I got the idea from here http://stackoverflow.com/a/5623492/2352671 – 101010 Jun 04 '14 at 17:53
  • See http://stackoverflow.com/questions/23613704/dividing-a-number-into-smaller-random-ints/23616638#23616638 for a possible solution with integers. – pjs Jun 04 '14 at 18:27

5 Answers5

4

First generate n random variables. Then sum them up: randomSum. Calculate coefficient sum/randomSum. Then multiply all random variables with that coefficient.

Integers would pose a problem... Rounding too (probably)

JaBe
  • 664
  • 1
  • 8
  • 27
  • I forgot to mention that.. and I am sorry.. I already edited the question.. I have to provide also a version of the algorithm with only unsigned integer. – Tarta Jun 04 '14 at 17:03
  • @Tarta So? This would not generate negative numbers, would it now? I actually like this answer better than mine – nl-x Jun 04 '14 at 17:15
  • Yes but the coefficient might not be an integer.. It's ok for the negative numbers. But not ok for integers. As I already wrote I am sorry I gave this further info only now.. – Tarta Jun 04 '14 at 17:20
1

You can generate n numbers with a normal distribution then normalize them to your sum

Ben
  • 2,065
  • 1
  • 13
  • 19
0

You can generate n values defined by this : ((Sum - sumOfGeneratedValues) / n - (numberOfGeneatedValue)) -+X (With X maximal deviance)

Example :

SUM = 100 N = 5 +- 10

Rand between 100 - 0 / 5 - 0 --> 20 +-10 (So bewteen 10 and 30)

Value1 = 17;

Rand between 100 - 17 / 5 - 1 ---> 21 +-10 (So between 11 and 31)

... etc

Deviance would make your random uniform :)

Orelsanpls
  • 22,456
  • 6
  • 42
  • 69
0

you have a loop, where the number of iterations is equal to the number of random numbers you want minus 1. for the first iteration, you find a random number between 0 and the sum. you then subtract that random number from the sum, and on the next iteration you get another random number and subtract that from the sub sum minus the last iteration

its probably more easy in psuedocode

int sum = 10;
int n = 5; // 5 random numbers summed to equal sum
int subSum = sum;
int[] randomNumbers = new int[n];

for(int i = 0; i < n - 2; i++)
{
    randomNumbers[i] = rand(0, subSum); // get random number between 0 and subSum 
    subSum -= randomNumbers[i];
}

randomNumbers[n - 1] = subSum; // leftovers go to the last random number
iedoc
  • 2,266
  • 3
  • 30
  • 53
  • wth. I really object you using your grace period to copy such a large part of my answer, making it look like I copied yours – nl-x Jun 04 '14 at 17:19
  • seriously dude? i posted my answer before you posted yours? who's copying? wtf – iedoc Jun 04 '14 at 17:20
  • You just happened to also write your pseudo code in c# style, and call it pseudo code? C++ even uses different array syntax. Don't get me wrong, don't REALLY mind it, but you could have noted it, to not make me look like a copy cat. – nl-x Jun 04 '14 at 17:22
  • This will cause the mean of the first element to be large, and the mean of the last element to be near zero. Although you could fix that problem by scrambling the order once the numbers have been generated. – nispio Jun 04 '14 at 17:22
  • nl-x, really though, i swear i had wrote the psuedocode before you posted your answer. i'm a c# developer, but this code should work in c++ as far as i know – iedoc Jun 04 '14 at 17:24
  • ok, then sorry for the accusation. We need to meet sometime if we are that much thinking alike – nl-x Jun 04 '14 at 17:33
  • haha, i suppose we do~ – iedoc Jun 04 '14 at 17:56
0

My C++ is very (very very) rusty. So let's assume you already know how to get a random number between x and y with the function random(x,y). Then here is some psuedocode in some other c derived language:

int n = ....; // your input
int sum = ....; // your input
int[] answer = new int[n];
int tmpsum = 0;
for (int i=0; i < n; i++) {
    int exactpart = sum/n;
    int random = (exactpart/2) + random(0,exactpart);
    int[i] = tmpsum + random > sum ? sum - tmpsum : random;
    tmpsum += int[i];
}
int[n-1] += sum - tmpsum;
nl-x
  • 11,762
  • 7
  • 33
  • 61
  • If I'm not mistaken, this is not guaranteed to reach `sum` in all cases. – nispio Jun 04 '14 at 17:27
  • @nispio oops, when writing this i actually deleted a bit of code too early :) ... thanks for noticing it. I've edited my answer – nl-x Jun 04 '14 at 17:29