生成总计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]