Get X random points in a fixed grid without repetition

Question

I'm looking for a way of getting X points in a fixed sized grid of let's say M by N, where the points are not returned multiple times and all points have a similar chance of getting chosen and the amount of points returned is always X.

I had the idea of looping over all the grid points and giving each point a random chance of X/(N*M) yet I felt like that it would give more priority to the first points in the grid. Also this didn't meet the requirement of always returning X amount of points.

Also I could go with a way of using increments with a prime number to get kind of a shuffle without repeat functionality, but I'd rather have it behave more random than that.

Answer 1

Essentially, you need to keep track of the points you already chose, and make use of a random number generator to get a pseudo-uniformly distributed answer. Each "choice" should be independent of the previous one.

With your first idea, you're right, the first ones would have more chance of getting picked. Consider a one-dimensional array with two elements. With the strategy you mention, the chance of getting the first one is:

P[x=0] = 1/2 = 0.5

The chance of getting the second one is the chance of NOT getting the first one 0.5, times 1/2:

P[x=1] = 1/2 * 1/2 = 0.25

You don't mention which programming language you're using, so I'll assume you have at your disposal random number generator rand() which results in a random float in the range [0, 1), a Hashmap (or similar) data structure, and a Point data structure. I'll further assume that a point in the grid can be any floating point x,y, where 0 <= x < M and 0 <= y < N. (If this is a NxM array, then the same applies, but in integers, and up to (M-1,N-1)).

Hashmap points = new Hashmap();
Point p;

while (items.size() < X) {
    p = new Point(rand()*M, rand()*N);
    if (!points.containsKey(p)) {
        items.add(p, 1);
    }
}

Note: Two Point objects of equal x and y should be themselves considered equal and generate equal hash codes, etc.