14

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

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

例如：Geneatare 3 总和为 11 的数。

范围：

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

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

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

可以像这样生成一个常数和的 N 个数字，例如： 生成总和为常数的随机数， 但我无法用范围来完成。

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

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

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

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

4

3 回答 3

9

首先，注意问题等价于：

生成总和为数字 y 的 k 个数字，使得 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算法对列表进行洗牌。（您可以在通过所需限制后中止算法）。

于 2013-11-09T14:33:09.077 回答
7

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

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

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

于 2013-11-09T14:31:35.020 回答
2

这个问题相当于随机分配超过2最小值 9 的3位置。

因此，您从最小值 (1/5/3) 开始，然后是循环2时间，生成 [0-2] （3位置）的（伪）随机值并增加索引值。

例如

  • 1/5/3 开始
  • 第一个随机=1 ...增量索引1 ... 1/6/3
  • 2nd random=0 ... 增量索引 0 ... 2/6/3

2+6+3=11

编辑

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

于 2013-11-09T15:21:22.383 回答