- randomized-algorithms search-problem
- Updated Sat, 25 Jun 2022 20:35:48 GMT

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

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

- +0 – Thanks. it is en.wikipedia.org/wiki/Reservoir_sampling an ever covered in Knuth... +1 For my purpose I just need filtering before applying algorithm and it works because it is en.wikipedia.org/wiki/Online_algorithm — Jun 27, 2015 at 06:48