在给定范围内生成 N 个随机数，总和为给定总和

Question

第一次来到 Stackoverflow。我希望有人可以帮助我搜索算法。

我需要在给定范围内生成 N 个随机数，总和达到给定总和！

例如：生成 3 个数字，总和为 11。

范围：

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

本示例生成的数字可能是：2、5、4。

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

可以生成 N 个不取模的常数和，如下所示： 生成总和恒定的随机数 但我无法用范围来完成这个任务。

或者通过生成 N 个随机值，将它们相加，然后将常数和除以随机和，然后将每个随机数与该商相乘如此处建议的。

主要问题，为什么我不能采用这些解决方案是我的每个随机值都有不同的范围，并且我需要这些值在范围内均匀分布（例如，在最小/最大处没有频率出现，如果我切断小于/大于最小值/最大值的值）。

我还想到了一个灵魂，取一个随机数（在该示例中，值 1,2 或 3），生成范围内的值（在最小值/最大值之间或最小值与其余总和之间，具体取决于哪个）更小），减去我给定总和的那个数字，并继续下去，直到所有东西都分配完毕。但这将是非常低效的。我真的可以使用一种固定算法运行时间的方法。

我正在尝试让它在 Java 中运行。但该信息并不那么重要，除非有人已经准备好了解决方案。我所需要的只是算法的描述或想法。

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]

- 将其洗牌并选择前两个元素。

(*) 请注意，可以使用 fisher-yates 算法来对列表进行打乱。 （超过所需限制后，您可以在中间中止算法）。

Answer 2

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

11 - 9 = 2，因此您必须在三个数字之间分配 2（例如：+2,+0,+0 或 +0,+1,+1）。

剩下的留给你了，经过这个转换之后创建均匀分布相对容易。

Answer 3

这个问题相当于在

2

位置上随机分配超过最小值 9 的

3

。

因此，您从最小值 (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 提到的。

Answer 4

Amit的回答很好，但我觉得有点难以理解。作为一个简单的示例，请考虑这样的情况：您需要 0 到 5 之间的三个随机数，加起来为 10。列出字母 a、b 和 c，各重复五次。然后对列表进行随机排列并仅查看前十个元素。 a、b 和 c 在总共十个字母中分别出现零到五次。第一个随机数是 a 的计数，第二个是 b 的计数，第三个是 c 的计数。总共十个。