java - 如何防止随机数重叠

Question

我想问一下，是否有任何方法可以确保这段代码在执行for循环函数时，产生0 < x < 1000范围内的随机数，不会重叠或重复。

这是它的一段代码:

Nodes(int noOfNodes){
    this.noOfNodes = noOfNodes;

    this.points = new Points[noOfNodes];

    for (int i = 0; i < noOfNodes; i ++) {

      points[i] = new Points(

              Integer.toString(i+1), 
              (float) (Math.random() * max) - min, 
              (float) (Math.random() * max) - min);
    }
    this.points=points;
}

注意:我使用了 float 类型，因为它是生成随机 float 的要求的一部分。

Answer 1

这会使点变得不均匀随机，这比听起来要棘手得多。我假设你的意思是生成这 2 个点是 Not Acceptable ，假设最小值为 0，最大值为 1:

• 点 [0.4, 0.8]
• 点 [0.7, 0.9]

因为它们重叠。

看似“明显”的方法(防止第 x 个节点找到仍然“开放”的范围并限制为仅在该范围内生成)意味着较高的节点可能要小得多。您可以通过在最后打乱生成的点来解决排序中的任何偏差，但您最终会得到一个更严格的“有些点非常大，但大多数点非常小”。那是你要的吗？ 90% 以上的时间，该算法会生成一个巨大的范围，而其余的都将是微小的范围？或者您希望算法生成大量中等大小的范​​围？

没有简单的答案。

我想要一个大范围和许多小范围

使用例如guava 的 RangeSet 类用于跟踪哪些范围被“占用”。对于所有“仍然开放”的范围，将它们添加到列表中，并建立一个等于开放范围大小的“因子”。因此，如果您打开 0.1-0.3 以及 0.4-0.5，则第一个范围的“权重”为 0.2，第二个范围的“权重”为 0.1，总共为 0.3。生成一个 0.0 到 0.3 之间的数字，用它来选择要限制自己的范围，然后生成 2 个随机数，如果第二个数字低于第一个数字，则翻转它们，然后您得到另一个范围，保证不重叠。将此范围添加到您的范围集中，然后从下一个节点重新开始。

许多大小大致相同的范围。

首先通过将可用的总范围除以要在其中生成的节点数来选择范围大小。因此，如果最小/最大为 0.0 和 1.0 并且您需要 5 个范围，则为 0.2。然后要么致力于精确地划分空间(此时随机不再是问题)，要么添加某种抖动函数来随机调整 0.2，例如在 50% 到 100% 之间，然后应用此算法，然后考虑到这一点调整剩余节点的中值范围大小(因此，如果您随机选择 0.1，则还剩 4 个节点可以生成超过 0.9 的节点)。这要复杂得多，并且有很多“好吧，你想要什么？”参与其中。