algorithm - 生成总和为 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]