Generate random numbers that sum up to n

user_1400869 0
Viewed 1231

How to generate between 1 and n random numbers (positive integers greater than 0) which sum up to exactly n?

Example results if n=10:

10
2,5,3
1,1,1,1,1,1,1,1,1,1
1,1,5,1,1,1

Each of the permutations should have the same probability of occurring, however, I don't need it to be mathematically precise. So if the probabilities are not the same due to some modulo error, I don't care.

Is there a go-to algorithm for this? I only found algorithms where the number of values is fixed (i.e., give me exactly m random numbers which sum up to n).

random algorithm
3 Answers

Imagine the number n as a line built of n equal, indivisible sections. Your numbers are lengths of those sections that sum up to the whole. You can cut the original length between any two sections, or none.

This means there are n-1 potential cut points.

Choose a random n-1-bit number, that is a number between 0 and 2^(n-1); its binary representation tells you where to cut.

0 : 000 : [-|-|-|-] : 1,1,1,1
1 : 001 : [-|-|- -] :  1,1,2
3 : 011 : [-|- - -] :   1,3
5 : 101 : [- -|- -] :   2,2
7 : 111 : [- - - -] :    4

etc.

Implementation in python-3

import random


def perm(n, np):
    p = []
    d = 1
    for i in range(n):
        if np % 2 == 0:
            p.append(d)
            d = 1
        else:
            d += 1
        np //= 2
    return p


def test(ex_n):
    for ex_p in range(2 ** (ex_n - 1)):
        p = perm(ex_n, ex_p)
        print(len(p), p)


def randperm(n):
    np = random.randint(0, 2 ** (n - 1))
    return perm(n, np)

print(randperm(10))

you can verify it by generating all possible solutions for small n

test(4)

output:

4 [1, 1, 1, 1]
3 [2, 1, 1]
3 [1, 2, 1]
2 [3, 1]
3 [1, 1, 2]
2 [2, 2]
2 [1, 3]
1 [4]
user_65654060

Use a modulo.

This should make your day:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main()
{
    srand(time(0));
    int n=10;
    int x=0; /* sum of previous random number */
    while (x<n) {
                int r = rand() % (n-x) + 1;
                printf("%d ", r);
                x += r;
    }
    /* done */
    printf("\n");
}

Example output:

10
1 1 8 
3 4 1 1 1 
6 3 1 
9 1 
6 1 1 1 1 
5 4 1
user_8034220

Generate Random Integers With Fixed Sum

Method One: Multinomial Distribution

Deviation cannot be controlled strictly within the desired range.

# Python
import numpy as np
_sum = 800
n = 16
rnd_array = np.random.multinomial(_sum, np.ones(n)/n, size=1)[0]
print('Array:', rnd_array, ', Sum:', sum(rnd_array))
# returns Array: [64 41 57 49 48 44 46 44 40 55 58 54 54 54 39 53] , Sum: 800

Method Two: Random Integer Generator Within Lower and Upper Bounds

To control the deviation

# Python
import random
def generate_random_integers(_sum, n):  
    mean = _sum / n
    variance = int(5 * mean)

    min_v = mean - variance
    max_v = mean + variance
    array = [min_v] * n

    diff = _sum - min_v * n
    while diff > 0:
        a = random.randint(0, n - 1)
        if array[a] >= max_v:
            continue
        array[a] += 1
        diff -= 1
    return np.array([int(number) for number in array])
_sum = 800
n = 16
rnd_array = generate_random_integers(_sum, n)
print('Array:', rnd_array, ', Sum:', sum(rnd_array))
# Returns Array: [45 46 46 58 53 77 33 53 39 38 44 51 33 60 75 49] , Sum: 800

Archived from http://sunny.today/generate-random-integers-with-fixed-sum/

user_34919910
Related