All binary combinations in a 2d Numpy

Question

I am trying to create a code that could generate all possible combinations of 0 and 1 in a numpy matrix excluding rotations. What do I mean rotation? I mean that below matrix data are in fact the same because it has the same data but rotated 90º, 180º and 270º.

I have been trying below code but I think i am not getting all combinations and I have some of them missing. Do you have any idea if this is the right way? Do you know if there is any more efficient way?

For example, considering dx=3 and dy=3

import numpy as np

def myfunction(data)
   print(data)

dx=3
dy=3
data = np.zeros([dx, dy], dtype=np.uint8)

y=0

for x in range(dx):
    for r in range(2):
        data[x, y] = r
        myfunction(data)
        for y in range(dy):
            for s in range(2):
                data[x, y] = s
                myfunction(data)

Thank you very much!

Answer 1

Here is a vectorized solution that can work for small matrix sizes; comments in the code illustrate a 3 by 3 case:

def get_binary_mats(n):
  # all possible n by n binary matrices up to rotation: 
  bin_mats = (np.bitwise_and(np.arange(2**(n*n))[:,None], 2 ** np.arange(n*n)) > 0)\
    .reshape(-1, n, n)
  # define a score for each matrix based on position of ones
  score = 2 ** np.arange(n*n).reshape(n,n)
  # array([[  1,   2,   4],
        #  [  8,  16,  32],
        #  [ 64, 128, 256]])
  score_arr = np.stack([np.rot90(score, k=k) for k in range(4)])
  # array([[[  1,   2,   4],
  #         [  8,  16,  32],
  #         [ 64, 128, 256]],

  #        [[  4,  32, 256],
  #         [  2,  16, 128],
  #         [  1,   8,  64]],

  #        [[256, 128,  64],
  #         [ 32,  16,   8],
  #         [  4,   2,   1]],

  #        [[ 64,   8,   1],
  #         [128,  16,   2],
  #         [256,  32,   4]]])

  scores = np.einsum("ijk,ljk->il", bin_mats, score_arr)
  _, idx = np.unique(scores.min(1), return_index=True)
  return bin_mats[idx,...]

The main idea is that we can take a "dot product" of an N by N binary matrix with an N by N matrix consisting of first N^2 powers of 2 (I call the latter the score matrix). When we do this, we get a unique integer for each possible binary matrix.

To account for rotations, we can take a "dot product" with 4 rotations of the "score" matrix, and associate each binary matrix to the minimum of the four results. We can refer to this minimum as a score of a binary matrix.

Finally, we can pick a matrix for each unique score with np.unique. For example, here is the output for n = 2:

array([[[False, False],
        [False, False]],

       [[ True, False],
        [False, False]],

       [[ True,  True],
        [False, False]],

       [[False,  True],
        [ True, False]],

       [[ True,  True],
        [ True, False]],

       [[ True,  True],
        [ True,  True]]])

As a sanity check, the number of binary matrices up to rotation lines up with this OEIS sequence for n up to 5:

%time assert [get_binary_mats(k).shape[0] for k in range(1, 6)] == [2, 6, 140, 16456, 8390720]
# takes 20 seconds on my machine