numpy：在方阵中查找非重叠块

Question

用一个例子介绍我的问题：我有一个 numpy 矩阵

     1 . . 1 .
     . 1 . . 1
A =  . . 1 . 1 
     1 . . 1 .
     . 1 1 . 1

为了更清晰的视觉效果，我使用点来表示零。只要我跟踪它，我就可以自由地重新排序矩阵的行和列，这表明它可以用块形式表示：

     1 1 . . .
     1 1 . . .
B =  . . 1 1 . 
     . . 1 1 1
     . . . 1 1

很明显，这个矩阵由两个不重叠的块组成，

1 1         1 1 .
1 1   and   1 1 1
            . 1 1

索引 B[0:2,0:2] 和 B[2:5,2:5].

有没有一种通用的方法可以找到原始矩阵中所有此类非重叠块的数量和索引A？ A 可以有不同的大小，但始终是正方形、对称的，并且只包含条目 1 和 0。

我有一种模糊的感觉，可能有某种巧妙的线性代数技巧可以做到这一点，但到目前为止我还看不到它。

Answer 1

感谢@Julien 在评论中提及图表和连接。经过一番挖掘后，这就是我的想法。

假设我们从我原来的 post 中的“无序”矩阵 A 开始：

import scipy
import scipy.sparse
import scipy.ndimage

# transform A to sparse format;
# use scipy graph methods to reorder it into "contiguous" block form
B = scipy.sparse.csr_matrix(A)
permut = scipy.sparse.csgraph.reverse_cuthill_mckee(B)
B = B[permut,:][:,permut].toarray() # transform back to normal numpy array

# using scipy.ndimage methods, relabel all "non-touching" features 
# in matrix B and extract their index slices
B, num_features = scipy.ndimage.label(B)
slices = scipy.ndimage.find_objects(B)

B 在此代码段的末尾（零用点表示）：

     1 1 . . .
     1 1 1 . .
B =  . 1 1 . .
     . . . 2 2
     . . . 2 2

slices:

[(slice(0, 3, None), slice(0, 3, None)),
 (slice(3, 5, None), slice(3, 5, None))]

代表我要求的块，只是顺序不同。

所用方法的文档：

csgraph.reverse_cuthill_mckee (Wikipedia)
ndimage.label
ndimage.find_objects

numpy：在方阵中查找非重叠块

numpy: Find non-overlapping blocks in square matrix

python

numpy

matrix

linear-algebra

scipy