给定范围内生成N个随机数，使它们的和等于给定的总和

Question

第一次来Stackoverflow，希望有人能帮我寻找一个算法。

我需要在给定的范围内生成N个随机数，使它们相加得到给定的总和！

例如：生成3个数字，它们相加得到11。

范围：

1. 值介于1和3之间。
2. 值介于5和8之间。
3. 值介于3和7之间。

此示例的生成数字可能为：2、5、4。

我已经搜索了很多，但找不到我需要的解决方案。

可以使用取模（modulo）方式生成具有恒定和的N个数字，如下所示：generate random numbers of which the sum is constant，但我无法使用它来处理范围。

或者通过生成N个随机值，将它们相加，然后将常量和除以随机和，然后使用该商乘以每个随机数 as proposed here。

主要问题是我不能采用上述解决方案的原因是，我每个随机值都有不同的范围，并且我需要这些值在范围内均匀分布（例如，在最小/最大值处没有频率发生，如果我截断小于/大于最小/最大值的值，则会发生这种情况）。

我还考虑过一种解决方案，即取一个随机数（在该示例中为1、2或3），在范围内生成该值（在min/max之间或在min和剩余总和之间，具体取决于哪一个更小），从给定总和中减去该数字，并继续进行操作，直到所有内容都分配完毕。但这将非常低效。我真的需要一个运行时间固定的算法。

我正在尝试在Java中运行它。但是，除非有人已经准备好了解决方案，否则这些信息并不重要。我只需要一个算法的说明或想法。

- user2971974

---

不可能。如果它们符合您的要求，它们就不是真正的随机。 - Hot Licks

@HotLicks - 我不同意，它们可能是随机的（暂且不考虑我们无法生成随机数字），但在所需随机化次数的自由度上较低。我认为这种说法与“无法在范围[0,10]内生成随机数-因为限制使真正的随机化变得不可能”是相同的。 - amit

@amit - 但是在你选择了前两个数字之后，第三个数字就不再是随机的了。 - Hot Licks

所以，你有两个随机数 - 仍然是随机的。 - amit

Answer 1

首先，需要注意的是问题等同于：

生成k个数字，它们的和为y，每个数字x_1，...，x_k都有一个限制。

第二个问题可以通过简单地将下限从数字中减去来实现 - 因此在您的示例中，它相当于：

生成3个数字，使得x1 <= 2; x2 <= 3; x3 <= 4; x1 + x2 + x3 = 2

请注意，第二个问题可以通过多种方式解决，其中之一是：

生成一个列表，每个元素重复h_i次 - 其中h_i是元素i的限制 - 打乱列表，并选择前面的元素。

在您的示例中，列表是：[x1，x1，x2，x2，x2，x3，x3，x3，x3] - 将其打乱并选择前两个元素。

(*) 注意，可以使用费雪耶茨算法来对列表进行洗牌。在达到所需限制后，您可以在中途停止该算法。

- amit

---

正是我所需要的，谢谢。但仍需考虑大 K 值和更大范围（如数百，例如 50-150）的复杂度以及列表的内存消耗。 - user2971974

你不一定需要创建列表。如果你只需要几个样本，可以使用虚拟列表，而无需洗牌。根据随机选择的位置，你可以获取元素（倒数、跳过标记元素等）。 - Karoly Horvath

用了几年时间才明白这个是如何工作的，但现在我明白了，我很欣赏这个优雅的解决方案。 - Eliezer Miron

Answer 2

将最小值相加。在这种情况下，1 + 5 + 3 = 9。

11-9 = 2，所以你必须在三个数字之间分配2（例如：+2，+0，+0或+0，+1，+1）。

我留下剩下的部分给你处理，经过这种转换后创建均匀分布相对容易。

- Karoly Horvath

---

这是一种方法，但不是我想要的方法。更具体地说，问题本身是这里的点的分布。但很抱歉，这是我的错（糟糕的示例或糟糕的问题描述）。 在另一个具有其他范围的示例中：

1. 1-3
2. 2-20
3. 1-3 并且总和为15，值1和2在大多数情况下会达到最大值。这不是我想要的。amits的解决方案是我心中所想的。根据范围大小，需要通过权重来分配点数。

- user2971974

@user2971974，你得到了答案吗？你是怎么解决的？请分享一下，我也想写类似的东西。 - user2888996

Answer 3

这个问题等价于在3个位置上的最小值9上随机分配超额的2。因此，您从最小值（1/5/3）开始，然后循环2次，在[0-2]（3个位置）之间生成一个（伪）随机值，并增加索引值。

例如：

- 开始1/5/3 - 第一个随机数=1 ... 增加索引1 ... 1/6/3 - 第二个随机数=0 ... 增加索引0 ... 2/6/3

2+6+3=11

编辑：

第二次阅读时，我明白了，这正是@KarolyHorvath提到的。

- Eugen Rieck