生成随机数，使它们相加的和为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

每个排列出现的概率应该相同，但我不需要它在数学上是精确的。所以如果由于某些模数错误导致概率不相同，我并不在意。

有没有一个通用算法可以解决这个问题？我只发现了一些固定值数量的算法（即，给我恰好总和为n的m个随机数）。

- D.R.

---

@ceejayoz：我也想到了这个算法，但是它看起来离“每个排列的概率相同”相差甚远，不是吗？很容易就有超过10个排列，但是“10”的概率只有1/10。 （我知道，我说过它不必数学上精确，但也不应该相差太远） - D.R.

只是想澄清一下 - 你说“数字”，但你的例子都是整数。你是否排除浮点解决方案？负值允许吗？零呢？ - pjs

我不确定为什么人们正在将这个问题投票关闭为“范围过大”，我该如何改进这个问题？请留下评论，谢谢！ - D.R.

对我来说，这看起来更像是一个[数学问题]而不是编程问题。 - Toby Speight

@TobySpeight：最终我想要的是C#代码，但我没有加C#标签，因为我对算法感兴趣，而不是特定的实现。算法问题不属于StackOverflow的一部分吗？至于尝试，如果我自己找不到方法，我就没有权利在这里发布吗？ - D.R.

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中

---

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]

- Milo Bem

---

谢谢您添加解释 - 现在这是一个非常好的答案。我们不需要一次生成决策树的所有_n_位 - 如果我们有随机位的来源，我们可以在需要时取它们。这可以避免巨大算术数字的开销，因为我们不会用于算术运算。 - Toby Speight

我喜欢你解决问题的方式，也很喜欢你演示例子的方式。 - Maytham Fahmi

说实话，对于像我这样的笨蛋，我希望你能够给变量起个有意义的名字，这样我就可以更好地理解代码。我想进行修改，但我不知道d是什么，np和p有什么区别等等。我想在p中设置一个值的上限，比如“找到5个加起来等于10的数字”。 - Josh Sanders

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/

- zelusp

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 

- user803422

---

这似乎对较短的序列有偏见；如果它从所有可能性中公平选择，我们预计大约一半的示例输出将以“1”开头，但实际上只有一个。 - Toby Speight