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.