title: How to generate a M random binary arrays efficiently in Python?
body: <p>I want to evaluate a binary function at M different locations. The binary functions is of dimension <code>D</code> so the function space to evaluate it is exponential <code>2^D</code> (i.e. its inputs are all <code>[0,1]^D</code> "strings"). I want its evaluation at <code>M</code> unique/different points that are evenly/randomly distributed in the input space. I know how to generate all permutations if I wanted (essentially just tack a 0 or 1 to all previous permutations that have already been evaluated. (Pseudo)code in the appendix). However, thats exponential and I only need a fraction <code>M</code> points, not all <code>2^D</code>. Is there a quick way to do it? I thought of generating the binary arrays randomly and then if there was a collision to try another value until it was unique. As in:</p>
  
  <pre><code>while i &lt; n:
      b_D = randomly_generate_bit_array_length(D) # simply selects each bit randomly with 1/2 prob of choosing 0 or 1.
      if not b_n in HashTable[b_D]:
          HashTable[b_D] = b_D
          i++
  </code></pre>
  
  <p>however, according to the answer I got <a href="https://cs.stackexchange.com/questions/70926/what-is-the-expected-run-time-of-an-algorithm-that-randomly-generates-n-unique-s/70927#70927">here</a> that algorithm seems exponential. Is there a better way to do this where the runtime of my algorithm is only <code>M</code> instead of something that depends exponentially on D?</p>
  
  <p>Notice that its not an acceptable answer to try to generate all permutations until we have <code>M</code> points because I need the permutations to be randomly distributed among the binary arrays. i.e. if we start from <code>[0,0,...,0]</code> then generate <code>[1,0,...,0]</code> until we have <code>M</code> is not what I want because most of my arrays will end with 0's and I want to get a unbiased distribution of them.</p>
  
  <hr>
  
  <p>To generate all permutations:</p>
  
  <pre><code>def _generate_input_data_full(D):
      '''
      full means generate all 2^D.
      '''
      D = D-1
      prev_all_permutations = [ [-1], [1] ]
      current_all_permutations = prev_all_permutations
      for k in range(D):
          current_all_permutations = []
          for prev_perm in prev_all_permutations:
              #print('prev_perm: ', prev_perm)
              for b in [-1,1]:
                  new_perm = prev_perm + [b]
                  current_all_permutations.append(new_perm)
          prev_all_permutations = current_all_permutations
  </code></pre>