algorithm - 给定二进制 MxN 矩阵和切换列的能力，最大化行相同性？

Question

如果你有一个由 1 和 0 组成的二进制矩阵，并且可以切换列(将列中的所有 1 更改为 0，将所有 0 更改为 1)，那么如何找到“纯”行的最大数量对于列切换的所有可能组合？ “纯”表示该行全为 0，或全为 1。

例如:

1 0

1 0

1 1

您可以切换任一列以获得 2 行“纯”行，这是您能做的最好的事情(同时切换两列也不是更好)，因此您返回 2(“纯”行的最大数量)。

我似乎无法找到一种有效的方法来做到这一点。到目前为止，我得到的唯一方法是使用一堆循环和蛮力，并通过检查一行的总和是否为 0(全 0)或 N(一行中的元素数)来检查相同性。

Answer 1

更新

经过 OP 的澄清，最大纯行问题是找到切换后变为 00...0 或 11...1 的最大行数。我已相应更新了我的解决方案。

请注意，我们有以下事实:

1. 如果两行r_i和r_j在切换后减少为纯行，那么我们必须从 r_i = r_j 开始。

2. 如果r_i ≠ r_j且r_i 重叠r_j(即它们对应的某些列是相同的)，那么它们都不能映射到纯行。

上述两个事实都直接来自以下观察:

Max number of "pure" rows is the same as the max number of identical rows

证明

我们声称构成最大纯问题解的所有行在矩阵 M 中必须相同。

假设我们有一个 m×n 矩阵 M，并且我们已经找到了最大纯行问题的解决方案。设行 r_i 和 r_j 是两个任意行，在切换后会减少为纯行。

观察到，在对列进行所有必要的切换操作后(用σ₁、σ₂表示) , ..., σ_k), r_i 和 r_j 都是“纯”行。即我们有以下内容:

σ1(σ2(...(σk(ri)...)) = σ1(σ2(...(σk(rj)...)) = 00...0

或

σ1(σ2(...(σk(ri)...)) = σ1(σ2(...(σk(rj)...)) = 11...1

因此，在应用所有这些切换操作后，r_i 和 r_j 将彼此相等。如果我们撤消最后一次切换(即，我们切换这些行的相同列条目)，则显然 r_i 和 < em>r_j 仍将映射到相同的输出。即我们有以下内容:

σ2(σ3(...(σk(ri)...)) = σ2(σ3(...(σk(rj)...))

如果我们继续撤消切换操作，我们可以得出结论:r_i = r_j。换句话说，如果您从 max-pure 问题的解决方案中选取任意行，这些行在开始时必须相同。

想法

给定一行r_i，如果它可以简化为纯行，比如00...0，那么我们知道另一行r如果r_i与r_jj不能减少到11...1 sub>(来自上面的事实 2)。我们只能希望另一行不与r_i重叠的r_k减少到11.. .1.

算法

根据前面的想法，我们可以有以下简单的算法来解决最大纯行问题。

我们首先扫描矩阵 M 的行，然后找到矩阵中所有唯一行(表示为 s₁, s ₂，...，s_k)。我们让count(si)表示s_i在M中出现的次数。 然后，我们循环遍历所有对 (s_i, s_j) 以确定最大纯行数，如下所示:

int maxCount = 0;

for each row si:
    for each  sj ≠ si:
        if (sj overlaps si)
            continue;
        else
            if (count(si) + count(sj) > maxCount)
                // We have found a better pair
                maxCount = count(si) + count(sj);    

return maxCount;

我们正在做O(n)在内部 for 循环中工作(用于按条目检查两行是否重叠)，并且循环结束 O(m<sup>2</sup>)最坏情况下的行数，因此算法的运行时间为 O(nm<sup>2</sup>) .