For each array position it is known if position filled or not.

How efficiently pick one free position with uniform probability?

That task happen during implementation of AI by Monter-Carlo method for board game.

I have in mind:

  • uniformly pick random index of array and check position, repeat until success - this method is extremely bad for mostly filled arrays
  • count free positions, uniformly pick random number from 1 to count and scan for that free position - this method require 2 arrays scans

Is it possible uniformly pick free position with only one scan?

From my intuition this algorithm produce biased solution toward clustered arrays:

  • uniformly select index and scal to one side until find free position

What if for each free position picking generate random permutation without cycles and travel across all elements by uniformly choosing index and recursively applying permutation until free position was found? I don't know if this algorithm leads to uniform picking. I don't know how to represent computationally efficient subset of permutations. This way may produce one pass solution...


1 Answer 1


Reservoir sampling can be used to uniformly pick a "free position with only one scan".


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.