CODEWITHSUNDEEP
arraysalgorithmfillrandom-access
user3548298
user3548298

Reputation: 196

Algorithm to fill an array randomly without collision

Say I have an array of N integers set to the value '0', and I want to pick a random element of that array that has the value '0' and put it to value '1'

How do I do this efficiently ?

I came up with 2 solutions but they look quite ineficient

First solution

int array[N] //init to 0s
int n //number of 1s we want to add to the array
int i = 0
while i < n
    int a = random(0, N)
    if array[a] == 0
        array[a] = 1
        i++
    end if
end while

It would be extremely inefficient for large arrays because of the probability of collision

The second involves a list containing all the 0 positions remaining and we choose a random number between 0 and the number of 0 remaining to lookup the value in the list that correspond to the index in the array. It's a lot more reliable than the first solution, since the number of operations is bounded, but still has a worst case scenario complexity of N² if we want to fill the array completely

Upvotes: 1

Views: 426

Answers (2)

Nelfeal
Nelfeal

Reputation: 13269

Your second solution is actually a good start. I assume that it involves rebuilding the list of positions after every change, which makes it O(N²) if you want to fill the whole array. However, you don't need to rebuild the list every time. Since you want to fill the array anyway, you can just use a random order and choose the remaining positions accordingly.

As an example, take the following array (size 7 and not initially full of zeroes) : [0, 0, 1, 0, 1, 1, 0]

Once you have built the list of zeros positions, here [0, 1, 3, 6], just shuffle it to get a random ordering. Then fill in the array in the order given by the positions.

For example, if the shuffle gives [3, 1, 6, 0], then you can fill the array like so :

[0, 0, 1, 0, 1, 1, 0]  <- initial configuration
[0, 0, 1, 1, 1, 1, 0]  <- First, position 3
[0, 1, 1, 1, 1, 1, 0]  <- Second, position 1
[0, 1, 1, 1, 1, 1, 1]  <- etc.
[1, 1, 1, 1, 1, 1, 1]

If the array is initially filled with zeros, then it's even easier. Your initial list is the list of integers from 0 to N (size of the array). Shuffle it and apply the same process.

If you do not want to fill the whole array, you still need to build the whole list, but you can truncate it after shuffling it (which just means to stop filling the array after some point).

Of course, this solution requires that the array does not change between each step.

Upvotes: 3

MBo
MBo

Reputation: 80197

You can fill array with n ones and N-n zeros and make random shuffling.

Fisher-Yates shuffle has linear complexity:

for i from N−1 downto 1 do
     j ← random integer such that 0 ≤ j ≤ i
     exchange a[j] and a[i]

Upvotes: 2

Related Questions