Filling a n*n array randomly with fill fraction p

[theMster]

I'm trying to fill a n*n array randomly with a fill percentage p (in decimal form i.e. 0.75 for 75%). The value in each random element should simply be set to boolean TRUE so it's the positions that need to be randomised.

I've tried doing th following.

Start Loop

Randomise new position
If new position is FALSE then set to TRUE and set m=m+1

If m = n*n*p then exit loop

Do Loop

The problem with this algorithm is that it scales as n^2 which is a problem since the size of my array can vary between 100*100 to 25000*25000 which means that the larger array takes roughly 62500 times as long to fill.

I thought of doing the following.

Subdivide the large array into a number of smaller ones. Then perform the above algorithm for each of the smaller arrays. Not sure though if that would be much quicker.

So I'm wondering if there is some other algorithm that would be quicker.

Cheers,
Pedro

[NotLKH]

Sorry, I was wondering if I'm understanding you correctly.

Are you saying:

Given an n x n boolean array, where 99 < n < 25001,
set Z of its cells to True such that

Z/n² <= p;
(Z+1)/n² >= p

Test with p = .75

Minimize the speed.



-Lou

[theMster]

Yes you have understood me correctly.

I want Z = INT(p*n^2)

The value of p varies from 0.01 to 0.99, but it might be quicker to construct an algorithm that sets Z=INT((1-p)*n^2) elements to TRUE if p>0.5 and then performs a NOT operation on the array.

Pedro