布尔矩阵行列置换：实现最小覆盖矩形分解的技术问询

嘿，针对你提出的布尔矩阵行列置换+最小矩形覆盖的问题，我结合实际场景给你拆解清楚：

我们已经有了能找出覆盖布尔矩阵所有1的最小不相交矩形集的算法，现在要做的是找到合适的行、列置换方式——把矩阵的行和列重新排列后，这个新矩阵能直接用刚才找到的最小矩形集完成覆盖，而且矩形之间互不重叠、恰好覆盖所有1。

用你提到的对象-属性场景来理解：每个对象对应矩阵的一行，每个属性对应一列，单元格为1表示该对象拥有此属性。我们的目标就是重新排序对象和属性，让拥有相同属性组合的对象聚在一起，相同属性组对应的列也聚在一起，这样就能用最少的矩形框出所有“对象-属性”的拥有关系。

这个置换的本质是归拢同类项：把属于同一个最小矩形的行（对象）和列（属性）分别连续排列。这样置换后的矩阵里，每个最小矩形都会变成一个连续的子矩阵，彼此之间没有重叠，且刚好覆盖所有1。

举个具体的对象-属性例子：

• 对象集合：{A, B, C, D}
• 属性集合：{X, Y, Z, W}
• 原始布尔矩阵（行=对象，列=属性）：

  X Y Z W
  A 1 0 1 0
  B 1 0 1 0
  C 0 1 0 1
  D 0 1 0 1
  

首先用已知算法找出最小不相交矩形集：这里是2个矩形，一个覆盖(A,B,X,Z)，另一个覆盖(C,D,Y,W)。

接下来做行列置换：

1. 行置换：把同属一个矩形的对象排在一起，比如先排A、B，再排C、D
2. 列置换：把同属一个矩形的属性排在一起，比如先排X、Z，再排Y、W

置换后的矩阵就变成了：

X Z Y W
  A 1 1 0 0
  B 1 1 0 0
  C 0 0 1 1
  D 0 0 1 1

这个矩阵里，两个最小矩形就是左上角和右下角的连续块，完美覆盖所有1，且没有重叠，完全符合要求。

1. 先找最小矩形集：用你已知的算法，得到覆盖所有1的最小不相交矩形集合R₁, R₂, ..., Rₖ
2. 行置换：将每个矩形Rᵢ包含的所有行连续排列（同一矩形内的行顺序可以任意调整，不影响结果）
3. 列置换：同理，将每个矩形Rᵢ包含的所有列连续排列（同一矩形内的列顺序也可任意调整）
4. 验证结果：置换后的矩阵中，每个Rᵢ都会对应一个连续的子矩阵，所有1都被覆盖，且矩形之间互不相交，数量保持最小的k

• 单个1形成的1x1矩形：对应的行和列可以放在任意位置，只要保证这个1的位置是独立的小矩形即可
• 同一矩形内的行/列顺序不影响最小覆盖的性质，可根据实际需求调整
• 置换后的矩阵会呈现清晰的“分块结构”，所有有效矩形都是连续的块，视觉上非常直观

内容的提问来源于stack exchange，提问作者Adam Ryczkowski