Generate an array of bit vectors with no repeated columns

user_6997665 0
Viewed 157

I have an array of dimensions [batch_size, input_dim] which needs to be filled only with 0 or 1. I need element in each column to be distinct from the rest of the columns. I have taken a approach like below:

 train_data = np.zeros(shape=[batch, input_dim])
 num_of_ones = random.sample(range(input_dim + 1), batch)
 for k in range(batch):
     num_of_one = num_of_ones[k]
     for _ in range(num_of_one):
         train_data[k][np.random.randint(0, input_dim)] = 1

Though this guarantees that no element is repeated (owing to the fact that each column has different number of 1's), there are still many combinations that are left out. For instance when num_of_one = 1, there are input_dim number of possibilities and so on. another downside of the method I have follwed is that both batch_size and input_dim have to be the same (else random.sample throws an error). I do not want to list down all possibilities as that would take forever to complete.

Is there any simple way to achieve the above stated problem?

numpy python
4 Answers

You could select a set of distinct numbers (look in itertools) between 0 and 2^input_dim, and use their binary representations to get the sequence of 0's and 1's for each value. Since the numbers selected would be distinct, their binary representations would be distinct as well.

user_5352750

Observe the binary representation of the numbers from 0 to 7:

000
001
010
011
100
101
110
111

Each row is different! So, all we have to do is convert each row to column. e.g.

arr = [
    [0, 0, 0, 0, 1, 1, 1, 1],
    [0, 0, 1, 1, 0, 0, 1, 1],
    [0, 1, 0, 1, 0, 1, 0, 1],
]

Also, observe that we have used all the unique possibilities. Now, with 3 rows, we can not add 2**3 + 1 th column.

In general, if cols > 2**rows, then we can not find unique representation.

You can do something like this:

rows = 3
cols = 8

if 2**rows < cols:
    print('Not possible')

arr = [[None] * cols for _ in range(rows)]

for col_idx in range(cols):
    binary = bin(col_idx)[2:]
    binary = binary.zfill(rows)

    for row_idx in range(rows):
        arr[row_idx][col_idx] = int(binary[row_idx])

for row in arr:
    print(row)

Time Complexity: O(rows * cols)

Space Complexity: O(rows * cols)

user_50998030

Why yours doesn't work

Yours has an issue with this line:

    for _ in range(num_of_one):
        train_data[k][np.random.randint(0, input_dim)] = 1

Because you select random rows to be set to 1, you could have these repeating, and it's not guaranteed that you'll have the right number of ones in each column, hence you can have duplicates. This is essentially no better, than randomizing the entire array, and hoping there are no duplicates.

Solution

You can achieve this via the magic of binary counting. Each of these columns are a different numbers binary representation. There are some limitations to this, as you would with any solution, where it's impossible to have all unique columns.

d = np.arange(input_dim)
random.shuffle(d)
train_data = (((d[:,None] & (1 << np.arange(batch)))) > 0).astype(float).T
print( train_data )
user_44414040

Your best bet is something like np.unpackbits combined with python's random.sample. random.sample will sample without replacement without creating a list of the input. This means that you can use a range object over arbitrarily large integers without any risk of problems, as long as the sample size fits in memory. np.unpackbits then converts the integers into unique bit sequences. This idea is a concrete implementation of @ScottHunter's answer.

batch_size = number_of_bits
input_size = number_of_samples

First, decide how many bytes you'll need to generate, and the max integer that you'll need to cover the range. Remember, Python supports arbitrary precision integers, so go crazy:

bytes_size = np.ceil(batch_size / 8)
max_int = 1<<batch_size

Now get your unique samples:

samples = random.sample(range(max_int), input_size)

Python integers are full blown objects with a to_bytes method that will prep your samples for np.unpackbits:

data = np.array([list(x.to_bytes(bytes_size, 'little')) for x in samples], dtype=np.uint8).T

The byte order matters if batch_size is not a multiple of 8: were going to trim the final array to size.

Now unpack and you're good to go:

result = np.unpackbits(data, axis=0)[:batch, :]

Putting it all together into a single package:

def random_bit_columns(batch_size, input_size):
    samples = random.sample(range(1 << batch_size), input_size)
    data = np.array([list(x.to_bytes(np.ceil(batch_size / 8), 'little')) for x in samples], dtype=np.uint8).T
    result = np.unpackbits(data, axis=0)[:batch, :]
    return result

I'm afraid I can't see a way out of using a list comprehension over the number of columns if you want to have the benefit of python's arbitrary precision integers.

user_29887300
Related