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

algorithm random java

2022-09-04 02:24:51

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

我需要在给定的范围内生成N个随机数，这些随机数的总和等于给定的总和！

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

范围：

此考试的生成数字可以是：2、5、4。

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

可以像这样生成像常量和的N个数字解调模：生成总和为常数的随机数，但我无法用范围完成。

或者通过生成N个随机值，将它们求和，然后将常量和除以随机和，然后将每个随机数与该商相乘，如这里所建议的那样。

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

我还想到了一个 soultion，取一个随机数（在该示例中，值为 1，2 或 3），在范围内生成值（介于最小值/最大值或最小值之间，其余部分取决于哪个值更小），减去我给定的总和中的该数字，并保持该值，直到所有内容都分布完毕。但那将是可怕的低效率。我真的可以使用一种算法运行时固定的方法。

我试图让它在Java中运行。但是该信息不是那个导入端，除非有人已经准备好了解决方案。我需要的只是一个算法的描述或想法。

答案 1

首先，请注意，该问题等效于：

生成总和为数字 y 的 k 个数字，这样x_1，...，x_k - 每个数字都有一个限制。

第二个可以通过简单地从数字中减少下限来实现 - 所以在你的示例中，它等价于：

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

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

生成一个每个元素重复的列表 - 其中元素的限制 - 随机排列列表，然后选择第一个元素。h_ih_ii

在您的示例中，列表是： - 随机排列并选择前两个元素。[x1,x1,x2,x2,x2,x3,x3,x3,x3]

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

答案 2

将最小值相加。在本例中为 1 + 5 + 3 = 9

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

我把剩下的留给你，在这个转换之后创建一个均匀的分布相对容易。