二维 Numpy 中的所有二进制组合

Question

我正在尝试创建一个代码，该代码可以在 numpy 矩阵中生成 0 和 1 的所有可能组合，不包括旋转。旋转是什么意思？我的意思是下面的矩阵数据实际上是相同的，因为它具有相同的数据但旋转了 90º、180º 和 270º。

我一直在尝试下面的代码，但我认为我没有得到所有的组合，而且我还遗漏了一些组合。你知道这是否是正确的方法吗？你知道有没有更有效的方法？

例如，考虑 dx=3 和 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)

非常感谢！

Answer 1

我不确定我的回答是否是最有效的方式，但无论如何。

我们可以使用 numpy.rot90 函数旋转每个矩阵。

让我们创建两个不同的字典，一个用于存储主矩阵，另一个用于存储主矩阵的旋转，这样我们就可以验证一个新矩阵是否只是先前找到的矩阵的旋转。

def Not_Rotated(dx, dy):
    import numpy as np
    from itertools import product

    Big_Matrix = np.array([[list(i[x:x+dx]) for x in range(0, len(i), dx)] for i in product("01", repeat=dx*dy)])  # Stores all possible combinations

    Main = dict()  # Stores not rotated
    Main_c = 0

    Rotations = dict()  # Stores rotated
    Rotation_c = 0

    for i in range(len(Big_Matrix)):  # Going through all combinations
        flag = 1  # A flag to check if this combination is rotated of previous ones or not. 1= is not rotated of previous ones. 0 = is rotated.
        for z in range(Rotation_c):
            if np.array_equal(Big_Matrix[i],Rotations[z]):  # Checking if this combination is rotated of previous ones or not
                flag = 0

        if flag:  # If this combination is not a rotation of previous ones
            Main[Main_c] = Big_Matrix[i]
            # Rotate it three times and store the matrices
            Rotations[Rotation_c] = np.rot90(Main[Main_c])
            Rotations[Rotation_c + 1] = np.rot90(Main[Main_c])
            Rotations[Rotation_c + 2] = np.rot90(Main[Main_c])
            Rotation_c += 3
            Main_c += 1
    return Main

Answer 2

这是一个适用于小矩阵大小的矢量化解决方案；代码中的注释说明了 3 x 3 的情况：

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,...]

主要思想是我们可以对 N×N 二进制矩阵与 N×N 矩阵进行“点积”，该矩阵由 2 的前 N^2 次幂组成（我将后者称为得分矩阵）。当我们这样做时，我们为每个可能的二进制矩阵得到一个唯一的整数。

为了考虑旋转，我们可以采用“分数”矩阵的 4 次旋转的“点积”，并将每个二进制矩阵与四个结果中的最小值相关联。我们可以将这个最小值称为二进制矩阵的分数。

最后，我们可以用 np.unique 为每个唯一分数选择一个矩阵。例如，这里是 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]]])

作为健全性检查，旋转的二进制矩阵的数量与 this OEIS sequence 一致，n 最多为 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

二维 Numpy 中的所有二进制组合

All binary combinations in a 2d Numpy

python

combinations

numpy

permutation