最大限度地行千篇一律给出一个二进制m×n矩阵，并切换列的能力？ [英] Maximize row-sameness given a binary MxN matrix and the ability to toggle columns?

问题描述

如果你有1和0的二进制矩阵，您可以切换列（改变全1到列0，而全0至1秒），你怎么发现的纯行的最大数量列切换的所有可能组合？ 纯意味着该行全0或全1。

If you have a binary matrix of 1s and 0s, and you are able to toggle columns (change all 1s to 0s in the column, and all 0s to 1s), how do you find the max number of "pure" rows for all possible combinations of column toggles? "pure" meaning the row is all 0s, or all 1s.

例如：

1 0

1 0

1

您可以通过切换栏获得2行是纯粹的，这是最好的，你可以做（​​切换这两个是不是更好），这样你就返回2（纯行的最大个数）。

You can toggle either column to get 2 rows that are "pure", which is the best you can do (toggling both is not better), so you return 2 (the max number of "pure" rows).

我似乎无法找出一个有效的方法来做到这一点。我到目前为止得到的唯一方法是一堆循环和暴力，并通过检查行的总和为0（全0）或N（元素的数量在一排）检查千篇一律。

I can't seem to figure out an efficient way to do this. The only way I've gotten so far is with a bunch of loops and brute force and checking for sameness by checking if the sum of a row is either 0 (all 0s) or N (the number of elements in a row).

推荐答案

从OP澄清后，最大纯行问题的的发现，成为行的最大数量为00 ... 0或11 ...... 1后切换的。我已经相应地更新我的解决办法。

Update

After clarification from the OP, the max-pure row problem is to find the max number of rows that become either 00...0 or 11...1 after toggling. I have updated my solution accordingly.

请注意，我们有以下的事实：

Note that we have the following facts:

1. 如果两行的研究<子>我 和研究<子>Ĵ 的切换后，减少到纯一行，那么我们就必须拥有的研究<子>我 = 研究<子>Ĵ 的开始。

1. If two rows r_i and r_j reduce to a pure row after toggling, then we must have r_i = r_j to start with.

如果研究<子>我 的≠的研究<子>Ĵ 和研究<子>我 的重叠的研究<子>Ĵ 的（也就是他们的一些相应的列是相同的），然后他们两个不能映射到纯一行。

If r_i ≠ r_j and r_i overlaps r_j (i.e. some of their corresponding column are the same), then both of them cannot map to a pure row.

两者的事实的上面直接来自以下观察：

Both of the facts above comes directly from the following observation:

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

我们要求所有构成的最大纯问题的解决方案中的行必须在矩阵M相同。

We claim that all the rows that constitute a solution of the max-pure problem must be identical in the matrix M.

假设我们有一个m乘n矩阵的 M 的，和我们已发现最大纯排问题的一个解决方案。让行的研究<子>我 和研究<子>Ĵ 的是，获得减少纯行切换后的两个任意行。

Suppose we are given a m-by-n matrix M, and we have found a solution of the max-pure row problem. Let rows r_i and r_j be two arbitrary rows that get reduce to pure rows after toggling.

观察以后，所有的列必要的反复操作（按指的σ<子> 1 的σ ₂ 的，...，σ<子> K 的），研究<子>我 和研究<子>Ĵ 的都是纯粹的行。即我们有以下几点：

Observe that after all the necessary toggling operation on the columns (denote by σ₁, σ₂, ..., σ_k), r_i and r_j are both "pure" rows. i.e. We have the following:

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

或

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

于是将所有这些切换操作后，研究<子>我 和研究<子>Ĵ 的将等于对方。如果我们的撤消的最后反复（即我们切换这些行的同一列项），这显然是双方的研究<子>我 和<的EM>研究<子>Ĵ 的将仍然映射到相同的输出。即我们有以下几点：

So after applying all these toggling operations, r_i and r_j will equal each other. If we undo the very last toggling (i.e. we toggling the same column entry of these rows), it is obviously that both r_i and r_j will still map to the same output. i.e. We have the following:

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

如果我们我们继续撤消切换操作，我们可以得出这样的结论的研究<子>我 = 研究<子>Ĵ 的。换句话说，如果你的最大纯问题的解决方案挑选任意行，这些行必须在开始的时候是相同的。

If we we continue undoing the toggling operations, we can conclude that r_i = r_j. In other words, if you pick any arbitrary rows from a solution of the max-pure problem, these rows must be identical in the beginning.

由于连续的研究<子>我 的，如果它可以减少对纯行，说00 ... 0，那么我们就知道另一行的研究<子>Ĵ 的不能被减少到11 ... 1，如果研究<子>我 的用的研究<子>Ĵ<重叠/子> 的（从上面的事实2）。我们只能希望，另一行的研究<子> K 的不与研究<子>重叠，我 的减少到11 .. 0.1。

Given a row r_i, if it can be reduce to the pure row, say 00...0, then we know that another row r_j cannot be reduced to 11...1 if r_i overlaps with r_j (from fact 2 above). We can only hope that another row r_k which does not overlap with r_i to reduce to 11...1.

从preceding的想法，我们可以有以下的简单算法，解决了最大纯行的问题。

From the preceding idea, we can have the following simple algorithm to solve the max-pure row problem.

我们第一次扫描过的矩阵M的行，然后找到所有的唯一的矩阵的行（通过的取值<子> 1 ，S <子>表示2 ，...，S <子> K 的）。我们让计数（SI）表示的次数的取值<子>我 的出现在M. 然后，我们遍历所有对（取值<子>我，S <子>Ĵ 的）确定为低于最大纯行号：

We first scan over the rows of matrix M, and then find all the unique rows of the matrix (denote by s₁, s₂, ..., s_k). We let count(si) denotes the number of times s_i appears in M. We then loop over all the pairs (s_i, s_j) to determine the max-pure row number as below:

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）工作在内部进行循环（对于入门明智的检查两行是否重叠），以及循环超过 0（M 2 ）在最坏的情况下，行，所以该算法的运行时间 0（NM 2 ）。

We are doing O(n) works in the inner for loop (for entry-wise checking whether two rows overlap), and the loops are over O(m2) rows in the worst-case, so the running time of the algorithm is O(nm2).

这篇关于最大限度地行千篇一律给出一个二进制m×n矩阵，并切换列的能力？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！