How to generate a M random binary arrays efficiently in Python?

I want to evaluate a binary function at M different locations. The binary functions is of dimension D so the function space to evaluate it is exponential 2^D. I want its evaluation at M 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 M points, not all 2^D. 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:

while i < 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++

however, according to the answer I got here that algorithm seems exponential. Is there a better way to do this where the runtime of my algorithm is only M instead of something that depends exponentially on D?

Notice that its not an acceptable answer to try to generate all permutations until we have M points because I need the permutations to be randomly distributed among the binary arrays. i.e. if we start from [0,0,...,0] then generate [1,0,...,0] until we have M 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.

---

To generate all permutations:

all_binary_arrays[0] = [0]
all_binary_arrays[1] = [1]
for k in range(M):
    for prev_permutation in all_binary_arrays:
        for i in [0,1]:
            all_binary_arrays.append(prev_permutation+[i])