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).
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]