生成总和为n的随机数

Question

如何生成 1 到 n 个随机数（大于 0 的正整数）且总和恰好为 n？

n=10 时的结果示例：

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

每个排列应该具有相同的发生概率，但是，我不需要它在数学上精确。因此，如果由于某些模误差而导致概率不同，我不在乎。

有这方面的首选算法吗？我只找到了值的数量是固定的算法（即，给我恰好 m 个随机数，总和为 n）。

Answer 1

将数字 n 想象成一条由 n 个相等且不可分割的部分组成的线。你的数字是这些部分的长度加起来的总和。您可以在任意两个部分之间剪切原始长度，也可以不剪切。

这意味着有n-1个潜在的切割点。

选择一个随机的 n-1 位数字，即 0 和 2^(n-1) 之间的数字；它的二进制表示告诉你在哪里剪切。

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

等等

---

在 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))

您可以通过为小n

生成所有可能的解决方案来验证它

test(4)

输出：

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]

Answer 2

生成具有固定和的随机整数

方法一：多项分布

偏差无法严格控制在所需范围内。

# 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

方法二：下限和上限内的随机整数生成器

控制偏差

# 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

存档自http://sunny.today/generate-random-integers-with-fixed-sum/

Answer 3

使用模数。

这应该让你开心：

#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");
}

输出示例：

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

Answer 4

聚会迟到了，但我认为您正在寻找狄利克雷多项分布的修改版本。不幸的是，目前 SciPy 似乎尚未实现从该分布中进行采样，因此我就此提出了一个问题。

在输出大于或等于 1 的约束下，以下函数将生成

m

正整数，总和为

n

:

import scipy.stats as sps

def random_split(n,m):
    p = sps.dirichlet.rvs(alpha=[1]*m, size=1)
    return 1+sps.multinomial.rvs(n=n-m, p=p[0], size=1)