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。换句话说，如果您从最大纯问题的解决方案中选择任意行，这些行在开始时必须相同。

想法

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

算法

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

我们首先扫描矩阵 M 的行，然后找到矩阵的所有 unique 行(用 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>) .