Avoid clash of positions in a matrix algorithm

Question

Assume you have a n x m matrix. In this matrix, you will be randomly positioning FOUR different objects say a, b, c, d. There will be many of each.

Now what is the best algorithm so that when they are randomly placed, their positions don't clash?

My approach would be to:

Randomly place them
Check through all the object's position, and if they clash, keep on moving until an empty space is found?

I am just wondering if there is any other efficient solution.

shapiro yaacov · Accepted Answer · 2015-05-13T12:14:10.550

1

If the end goal is to fill the board, you could just choose for each space on the matrix which type goes on it (the choice is random).

To add an option of an empty space, add a fifth option of NO_TYPE.

If the number of appearances is known, try this:

Create a list of size n X m (call it L) with values 1..L.
For each appearance, choose randomly from the list ( something like pos = rand(L) and the remove that value form the list (don't forget to decrease L).
Do this as many times as the necessary.

edited May 13 '15 at 12:14

answered May 13 '15 at 11:57

shapiro yaacov

2,308
2
26
39

And what if one has a fixed amount, like say if a has to be present five times? – VideoGamingIOs May 13 '15 at 12:04

vib · Answer 2 · 2015-05-13T12:54:37.963

A variation on the other answer, without creating additional structure (and with a better time complexity) :

Let assume that you have objects a_1, .., a_K (in your case K=4) and each of them has to be present n_k times, with n_1 + .. + n_K <= n*m. You can fill the matrix as follows, in pseudocode :

Initialize X as an empty n*m matrix
Initialize n as a vector of length l with n[l] = n_l
Set N = 0
For i = 1; i <= n; i++
    For j = 1; j <= m; j++
        Draw t at random uniformly on [0,1]
        For l = 1; l <=k; l++
            Set x_l = n[l] / (n*m-N)
            If (t <= x_l)
                Set X[i][j] = a_l
                Set n[l] = n[l]-1
                Escape the loop on l
     Set N = N+1

This will work better than your approach if you have many objects to place as you never reject placements. If you don't, then your approach is fine.

score 0 · Answer 3 · edited May 23 '17 at 12:21

If you have an algorithm that can generate a sequence of random positions that don't clash in your array, then you can easily generate however many positions you need for a then b then c then d etc.

You can accomplish this with this algorithm:

Generate a random prime number p that is greater than n * m
Generate a random number r in the range [0, n * m)
while(need more numbers)
{
    // output a position:
    yield x = r % n, y = r / n

    // generate the next position:
    r = (r + p) % (n * m)
}

The positions will never overlap because there are no common factors between p and n * m. It will produce a Full Cycle over n * m

For how to generate a random prime number, see this StackOverflow question:

Generate Random Prime number in C/C++ between 2 limits

If p is prime, then it will be relatively prime with n * m

Avoid clash of positions in a matrix algorithm

3 Answers3