generate random numbers of which the sum is constant

Question

I am thinking if there is anyway to generate a set of random numbers of which the sum is always a constant. For example, 20 can be divided into 5 numbers ( 1, 2,3,4,10) I don't care what each of the 5 numbers is as long as their sum is equal to 20. Is there anyway to do so programmatically?

Answer 1

To get a uniform distribution, the trick is to think of your sum as a number line, and rather than generating random numbers for the segments, generate n-1 numbers as points along the line, and subtract to get the segments. Here's the function from ojrandlib:

static int compare(const void *a, const void *b) {
    return *(int*)a - *(int*)b;
}
void ojr_array_with_sum(ojr_generator *g, int *a, int count, int sum) {
    int i;
    for (i = 0; i < count-1; ++i) { a[i] = ojr_rand(g, sum+1); }
    qsort(a, count-1, sizeof(int), compare);
    a[count-1] = sum;
    for (i = count-1; i > 0; --i) { a[i] -= a[i-1]; }
}

ojr_rand(g, limit) generates a uniform random integer from 0 to limit-1. This function then fills the array a with count random integers that add to sum. Shouldn't be too hard to adapt this to any other RNG.

Answer 2

This method does the job, and also allows controlling the "difference degree" between the values (e.g. if you want the array values to be close one to another)

/**
     * Create array of positive integers which exactly sums to a given (integer) number.
     * @param {Number} number of items
     * @param {Number} sum  required sum
     * @param {Number} [d=100] difference degree between the values (0..100)
     */
    randomSumArray: function(len, sum, d) {
        var _sum = 0;
        var arr = [];
        var n, i;

        if (!d && d !== 0) {
            d = 100;
        }

        for (i = 0; i < len; i++) {
            var from = (100 - d) * 1000,
                to = (100 + d) * 1000,
                n = Math.floor(Math.random() * (to - from + 1) + from); //random integer between from..to

            _sum += n;
            arr.push(n);
        }

        var x = sum / _sum;

        _sum = 0; //count sum (again)
        for (var i = 0; i < len; i++) {
            arr[i] = Math.round(arr[i] * x);
            _sum += arr[i];
        }

        var diff = sum - _sum;

        // Correct the array if its sum does not match required sum (usually by a small bit)
        if (diff) {
            x = diff / Math.abs(diff); //x will be 1 or -1
            var j = 0;
            while (diff && j < 1000) { //limit to a finite number of 'corrections'
                i = Math.floor(Math.random() * (len + 1)); //random index in the array
                if (arr[i] + x >= 0) {
                    arr[i] += x;
                    diff -= x;
                }
                j++;
            }
        }

        return arr;
    }

Answer 3

this is a bit of a Trick but still :)
i present this as a possible idea, not saying it is the best
(and mostly, you will need integers so it wont work anyway)

If the needed random numbers are not required integers:
then you can generate N random numbers between [0,1] and then normalize the array to your S :)

for(i=0; i<N; i++)
   arr[i] = rand;

cursum = 0;
for(i=0; i<N; i++)
   cursum+=arr[i];

norm = S / cursum;

for(i=0; i<N; i++)
    arr[i] *= norm;

Answer 4

If the numbers Generated are not necesserily Positive or whitin a range.
you can calculate the last number can be S - SUM(A1..A[N-1])

Selection of N-1 random numbers is obviously uniform,
and because the last number is anyway dependent on the rest of the numbers
(each set has only one option for the last number).

the uniformitty is not hindered.

Arr = new int[N];

int sum=0;
for(i=0; i<N-1; i++)
{
    int x = getRandomInt();
    sum += x;
    Arr[i] = x;
}
Arr[N-1] = S - sum;
return Arr;

Answer 5

Use a library function to get the random numbers.

Now the random number you want is the generated random number mod the allowed sum.

Next you decrement the allowed sum by the number you just generated.

Let's say the first random number your library random number generator returns is 109.

So your first random number is 109 mod 20 = 9. Update your allowed total to 20 -9 = 11.

You keep going until your allowed sum is zero.

Note that I assume the number 5 you mentioned is just an example. If you want the number of random numbers to be exactly 5 you might have to modify this method.

Answer 6

In my case I had to do this for array of values, that takes Sum and splits it into range of numbers at random.

    <html>
<script type="text/javascript">
function f(){
var array = [{
    order: '1-2480831',
    value: 2040
}, {
    order: 'BAESYS-2012-0001',
    value: 570
}, {
    order: 'BAESYS-2012-0002',
    value: 773
}, {
    order: '1-3840231',
    value: 299
}, {
    order: '1-3840298',
    value: 1609
}, {
    order: '1-3841519',
    value: 1940
}];

    var splitInto = 3;

    document.write("[");
    for (i=0; i<array.length; i++)
    {
        document.write("{ Id : '"+array[i].order+"', Data : [");
    var result = RandGenerator(splitInto,array[i].value);
    var sum = 0;
            for(ii =0;ii<result.length; ii++){
                sum += result[ii];
            document.write(result[ii]+',');
            }
            document.write("]},");
    }
    document.write("]");
}

function RandGenerator(count, sum) {
    var a = [];
    for (iii = 0; iii < count-1; iii++) 
        { 
            a[iii] = getRandToValue(sum);
            sum -= a[iii];
        }
    a[count-1] = sum;
    return a;
}

function getRandToValue(maxRand)
{
    var random = Math.random();
    var computed = (maxRand)*random;
    return computed;
}

f();
</script>
</html>

Answer 7

yes! try this algorithm

num1=rand()%20;  
num2=rand()%(20-num1);  
num3=rand()%(20-num1-num2);  
num4=rand()%(20-num1-num2-num3);  
num5=20-num4-num3-num2-num1;  

so for sure the five numbers are random and they sum up to 20
[you can do this using loop if you want]

In general you can first randomly generate the number of numbers[n] that will sum up to the number in hand[K]

 n=rand()%k;--assuming the number of rand numbers you want are between 1 and k[sum]
    n1=rand()%k;
    n2=rand()%(k-n1)
    .
    .
    nn-1=rand()%(k-n1...-nn-2)
    nn=k-n1-n2...nn-1

I hope that will help you!