title: Fast random selection algorithm
body: <p>Given an array of true/false values, what is the most efficient algorithm to select an index with a true value at random.  </p>
  
  <p>A sketch simple algorithm is</p>
  
  <pre><code>a &lt;- the array
  c &lt;- 0
  for i in a:
      if a[i] is true: c++
  e &lt;- random number in (0, c-1)
  j &lt;- 0
  for i in e:
      while j is false: j++
  return j
  </code></pre>
  
  <p>Can anyone come up with a faster algorithm?  Maybe there is a way to only walk through the list once even if the number of true elements is not known at first?  </p>