<p>For each array position it is known if position filled or not.</p>

<p>How efficiently pick one free position with <em>uniform probability</em>?</p>

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

<p>I have in mind:</p>

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

<p>Is it possible uniformly pick free position with only one scan?</p>

<p>From my intuition this algorithm produce biased solution toward clustered arrays:</p>

<ul>
<li>uniformly select index and scal to one side until find free position </li>
</ul>

<p>What if for each <em>free position picking</em> 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... </p>

<randomized-algorithms><search-problem>
Efficiently picking free position from array with uniform probability.
gavenkoa
# Efficiently picking free position from array with uniform probability.

(Asked by: username_0 on 2015-06-26)

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

**Tags:** randomized-algorithms, search-problem


---

## 0 answers

