Efficiently picking free position from array with uniform probability.

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...

Asked by user5916 (103 )
Jun 26, 2015 at 22:11