title: Efficient random generator for very large range (in python)
body: <p>I am trying to create a generator that returns numbers in a given range that pass a particular test given by a function <code>foo</code>. However I would like the numbers to be tested in a random order. The following code will achieve this:</p>
  
  <pre><code>from random import shuffle
  
  def MyGenerator(foo, num):
      order = list(range(num))
      shuffle(order)
      for i in order:
          if foo(i):
              yield i
  </code></pre>
  
  <p><strong>The Problem</strong></p>
  
  <p>The problem with this solution is that sometimes the range will be quite large (<code>num</code> might be of the order <code>10**8</code> and upwards). This function can become slow, having such a large list in memory. I have tried to avoid this problem, with the following code:</p>
  
  <pre><code>from random import randint    
  
  def MyGenerator(foo, num):
      tried = set()
      while len(tried) &lt;= num - 1:
          i = randint(0, num-1)
          if i in tried:
              continue
          tried.add(i)
          if foo(i):
              yield i
  </code></pre>
  
  <p>This works well most of the time, since in most cases <code>num</code> will be quite large, <code>foo</code> will pass a reasonable number of numbers and the total number of times the <code>__next__</code> method will be called will be relatively small (say, a maximum of 200 often much smaller). Therefore its reasonable likely we stumble upon a value that passes the <code>foo</code> test and the size of <code>tried</code> never gets large. (Even if it only passes 10% of the time, we wouldn't expect <code>tried</code> to get larger than about 2000 roughly.)</p>
  
  <p>However, when <code>num</code> is small (close to the number of times that the <code>__next__</code> method is called, or <code>foo</code> fails most of the time, the above solution becomes very inefficient - randomly guessing numbers until it guesses one that isn't in <code>tried</code>.</p>
  
  <p><strong>My attempted solution...</strong></p>
  
  <p>I was hoping to use some kind of function that maps the numbers <code>0,1,2,..., n</code> onto themselves in a roughly random way. (This isn't being used for any security purposes and so doesn't matter if it isn't the most 'random' function in the world). The function here (<a href="https://stackoverflow.com/questions/48205823/create-a-random-bijective-function-which-has-same-domain-and-range">Create a random bijective function which has same domain and range</a>) maps signed 32-bit integers onto themselves, but I am not sure how to adapt the mapping to a smaller range. Given <code>num</code> I don't even need a bijection on <code>0,1,..num</code> just a value of <code>n</code> larger than and 'close' to <code>num</code> (using whatever definition of close you see fit). Then I can do the following:</p>
  
  <pre><code>def mix_function_factory(num):
      # something here???
      def foo(index):
          # something else here??
      return foo
  
  def MyGenerator(foo, num):
      mix_function = mix_function_factory(num):
      for i in range(num):
          index = mix_function(i)
          if index &lt;= num:
              if foo(index):
                  yield index
  </code></pre>
  
  <p>(so long as the bijection isn't on a set of numbers massively larger than <code>num</code> the number of times <code>index &lt;= num</code> isn't True will be small).</p>
  
  <p><strong>My Question</strong></p>
  
  <p>Can you think of one of the following:</p>
  
  <ul>
  <li>A potential solution for <code>mix_function_factory</code> or even a few other potential functions for <code>mix_function</code> that I could attempt to generalise for different values of <code>num</code>?</li>
  <li>A better way of solving the original problem?</li>
  </ul>
  
  <p>Many thanks in advance....</p>