CODEWITHSUNDEEP
algorithmmatrixshuffle
Arsen Mkrtchyan
Arsen Mkrtchyan

Reputation: 50712

Randomly choose one cell from the grid and mark until some condition happen

I have NxN boolean matrix, all elements of which have initial state false

bool[][] matrix = GetMatrix(N);

In each step of the loop, I want to choose one cell (row i, column j) uniformly at random among all false cells, and set it to true until some condition happen.

Which method to use? I have this two ways in mind.

Uses O(N^2) additional memory, and initialization take O(N^2) time

And second

This way doesn't use any additional memory, but I have a difficulty to estimate performance... can it be a case, when all elements except one are set, and random repeats a lot of times looking for free cell? Am I right, that as soon as random theoretically works uniformly, this case should not happen so often?

Upvotes: 1

Views: 433

Answers (2)

Save
Save

Reputation: 11938

I'll try to reply to your questions, with a worst case scenario anaysis that happens when, as you have pointed out, all cells but one are taken.

Let's start by noting that p = P(X = m) = 1/N^2 . From this, we obtain that the probability that you'll have to wait k tosses before getting the desired result is P( Y = k) = p * (1-p)^(k-1) . This means that, for N = 10 you will need 67 random numbers to have a probability greater than 50% to get yours, and 457 to have a probability greater than 99%.

The general formula that gives you the number k of tosses needed to get the a probaiblity greater than alpha to get your value is:

k > (log(1 - alpha) / log(1-p)) -1

where p is define as above, equal to 1/N^2

That could get much worse with N getting bigger. You could think about creating a list of the indices you need and get one randomly for it.

Upvotes: 1

David Eisenstat
David Eisenstat

Reputation: 65458

Generate random i from 0...(N^2-1) and if (i/N, i%N) is set in matrix, repeat random generation until founding unset element.

The analysis of this algorithm is the same as the coupon collector's problem. The running time is Theta(n^2 log n).

Upvotes: 1

Related Questions