如何快速寻找二元矩阵中存在重复行的最大列子集

给定每列至少含两个1的二元矩阵，要找到最大列子集使诱导子矩阵存在重复行，核心思路是寻找差异列最少的行对，具体步骤如下：

• 遍历矩阵中所有行对（r₁, r₂），其中r₁≠r₂；
• 对每个行对，计算它们的差异列集合：即所有满足r₁[c]≠r₂[c]的列c；
• 找到差异列数量最少的行对，记其差异列集合为D；
• 最大列子集即为所有不在D中的列——移除D后，r₁和r₂在剩余列上完全相同，满足子矩阵存在重复行的要求；
• 若存在多个行对的差异列数量相同且最少，任选其一即可，对应的列子集大小一致。

原理说明 #

最大列子集等价于移除最少的列来让某两行变得完全相同。因为列子集的大小=总列数-移除的列数，所以要最大化子集大小，就需要最小化移除的列数——而最少的移除列数就是任意两行之间的最小差异列数。

示例验证（基于你提供的矩阵） #

原矩阵共7列：

[[0 1 1 0 1 1 1]                                                                                 
 [1 0 0 0 0 0 1]                                                                                 
 [1 1 0 1 0 0 0]
 [1 0 1 0 1 0 0]
 [0 0 0 1 0 1 1]
 [1 1 0 0 1 0 1]
 [0 1 0 1 0 0 0]]

对比行1（[1,0,0,0,0,0,1]）和行5（[1,1,0,0,1,0,1]），差异列仅为列1、列4（共2个）。移除这两个列后，剩余列是0、2、3、5、6，对应的子矩阵中这两行完全相同，且该子集大小为5，比你示例中的4列子集更大，是符合要求的最大子集。

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