How can I prevent random number from overlapping

Question

I would like to ask, if there is any method on ensuring this piece of code, which produces random number within a range of 0 < x < 1000 to not overlap or have duplicate when undergoing through the for loop function.

Here is a piece of code of it:

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;
}

Note: I used float type as it's part of the requirement to generate random float numbers.

Answer 1

That would make the points non-uniform random, this is a lot trickier than it sounds. I assume you mean that generating these 2 points would not be acceptable, assuming min is 0 and max is 1:

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

because they overlap.

The seemingly 'obvious' way to do it (prevent the xth node to find a range that is still 'open' and restrict to only generate within that) means that higher nodes are likely to be far smaller. You can solve any bias in ordering by shuffling the generated points at the very end, but you're going to end up with a more rigid 'some points are very large, but most are quite small'. Is that what you want? That 90%+ of the time, this algorithm generates one huge range and all the rest will be tiny ranges? Or would you prefer that the algorithm generates a large number of medium-sized ranges?

There are no easy answers.

I want one large range and many small ones

Use e.g. guava's RangeSet class to keep track of which ranges are 'occupied'. For all the 'still open' ranges, add them to a list, and establish a 'factor' that is equal to the open range's size. So, if you have 0.1-0.3 open as well as 0.4-0.5, then the 'weight' of the first range is 0.2, of the second it is 0.1, for a total of 0.3. Generate a number between 0.0 and 0.3, use that to pick which range to restrict yourself to, then generate 2 random numbers, flip em if the second is lower than the first, and you got yourself another range, guaranteed not to overlap. Add this range to your rangeset and start all over again for the next node.

Many roughly equally sized ranges.

First pick the range size, by dividing the total range available to you by the # of nodes you want to generate within. So, if the min/max is 0.0 and 1.0 and you need 5 ranges, it's 0.2. Then either commit to dividing up the space precisely (at which point random is no longer a thing at all), or add some sort of jitter function which will adjust the 0.2 randomly, e.g. between 50% to 100%, then apply this algorithm, then adjust your median rangesize for the remaining nodes by taking this into account (so if you randomly went with an 0.1, you have 4 left to generate over 0.9). This is way more complicated and has a ton of 'well, what do you want?' involved.

Answer 2

What you can do is maintain a List of float values that range from 0 to 1000. Then you can remove a value at a given random index and continue.

        Nodes(int noOfNodes) {
            Random random = new Random();

            List<Integer> positions = IntStream.rangeClosed(0, 1000)
                    .boxed()
                    .collect(Collectors.toList());

            this.noOfNodes = noOfNodes;

            this.points = new Points[noOfNodes];

            for (int i = 0; i < noOfNodes; i ++) {
                if (positions.size() < 2) {
                    throw new IllegalStateException("No more positions available.");
                }
                float first = positions.remove(random.nextInt(positions.size()));

                float second = positions.remove(random.nextInt(positions.size()));


                points[i] = new Points(Integer.toString(i+1), first, second);
            }
            this.points = points;
        }