使用最小行和列切换将 NxN 二进制矩阵转换为零矩阵
这是关于我发布的关于将一个 NxN 二进制矩阵转换为另一个矩阵的问题。我问的问题是一个代码挑战问题。然而，在如何通过行和列切换进行矩阵转换？中提出了类似的问题。我经历了该线程，并获得了一些关于如何解决问题的想法。 我在这里重申一下这个问题。
“我想编写代码来解决以下问题。我计划使用 C、C++、Java 或 Python，具体取决于哪一个提供更方便的解决方案。 给定两个 NxN (1 <= N <= 2000) 个二元矩阵（每个元素为 1 或 0 的矩阵），A 和 B。问题是使用最小数量的允许的操作。 允许的操作是：
1. 我们可以切换一行，
这将切换该行中的所有值，即该行中的 1 更改为 0，0 更改为 1
2. 我们可以切换一列，
这将切换该列中的所有值，即将该列中的 1 更改为 0，将 0 更改为 1。
如果没有解决方案，我们打印 -1"
但是，我有以下疑问。
我知道找到将 A 转换为 B 所需的最小切换次数的第一步是计算 A XOR B 。结果中的 1 是必须切换的地方，换句话说，必须使用最小数量的行和列切换将 A XOR B 转换为零矩阵。但是，我不清楚 A XOR B 如何转换为零矩阵。 ，使用最小数量的行和列切换，有人可以解释一下吗？
谢谢。
This is about the question i posted regarding converting one NxN binary matrix to another . The question i asked is a code-challenge problem . However, a similar question was asked at How to do matrix conversions by row and columns toggles?. I went through that thread,and have gained some idea about how to go about solving the problem.
I restate the problem here.
"I want to write code to solve the following problem. I am planning to use C, C++, Java or Python, depending on whichever allows a more convenient solution.
Given two NxN (1 <= N <= 2000) binary matrices (A matrix each of whose element is either a one or a zero), A and B. The problem is to transform A into B, using the minimum number of permissible operations.
The permissible operations are:
1. We can toggle a row,
which will toggle all values in that row, i.e. it will change 1 to 0 and 0 to 1 in that row
2. We can toggle a column,
which will toggle all values in that column, i.e. it will change 1 to 0 and 0 to 1 in that column.
If no solution is possible we print -1"
However, i have the following doubt.
I understood that the first step in finding the minimum number of toggles required to transform A to B is calculating A XOR B .The 1's in the result are the places which have to be toggled, in other words A XOR B has to be transformed to a zero matrix using the minimum number of row and column toggles . However, its not clear to me, how A XOR B is to be transformed to zero matrix , using the minimum number of row and column toggles. Could someone please shed some light on that ?
Thank You.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
相当简单的任务。
首先，我们应该明白多次切换行或列是没有意义的。为了更好地理解，我们这样表示状态：每个单元格中有 0 或 1，并且总是以模 2 求和结果：
其中
row_switched和column_switched是次我们交换第 i 行和第 j 列。现在很清楚，它们的值应该是 0 或 1 以获得最少的开关数量。但这实际上构成了……一个方程组！我们知道初始状态（给定），我们知道最终状态（零），我们只需要针对
r[i]和c[j]求解系统！不幸的是，由于模数的原因，它的求解仍然很复杂，而且它不包含 r[i] 和 c[j] 隐含的约束（0 或 1）。
让我们在没有模数的情况下重写这些条件：
为每个单元写出这个条件后，我们就得到了一个由 N^2 方程组成的超定义系统。我们通过下面的方法来解决。很明显，如果我们知道
row_switched[0]的值，那么我们就会知道整个column_switched[]数组的值，因为它们是由方程，其中有row_switched[0]参与。然后也很容易推断出每一行的值。但我们只有两个
row_switched[0]变体：0 和 1。让我们尝试每个变体（请参见下面的注释），并为每个变体计算两个数组！然后我们应该检查所有方程是否成立，并选择满足整个系统且具有较少开关的两组方程之一。如果两者都不满足，那么，这就是无解的。尝试解决这个问题，呵呵：
这样就解决了。我希望你只是为了尝试而做+1。 :)
关于为什么这是最少可能的开关数量的问题。事实上，任何有效数量的开关都应满足上述方程组（以 0 和 1 作为值的约束）。但该系统的解决方案不超过两个，并且我们在上面的算法中找到了所有解决方案。所以，上面的算法肯定会找到最小的。
注意：
在我看来，我们只能尝试其中的一套。如果其中一个通过了系统，另一个也应该通过。一组是另一组的否定，所以我们只选择开关数量较少的一组。开关总数为2N。但这只是似乎，并且比其他部分不太清楚。
Fairly easy task.
First, we should understand that there is no sense in switching a row or a column more than once. For better understanding, we denote state like that: each cell has 0 or 1 in it and always take result of the sum with modulo 2:
where
row_switchedandcolumn_switchedare numbers of times we switched i-th row and j-th column. Now it's clear, that their values should be 0 or 1 to get minimal number of switches.But that actually makes... a system of equations! We know initial states (given), we know final states (zeros), we only need to solve the system against
r[i]andc[j]!Unfortunately, it's still complex to solve because of moduli and because it doesn't include constraints implied on
r[i]andc[j](being 0 or 1).Let's rewrite these condition without modulus:
Having written this for each cell, we have gotten an overdefined system of N^2 equations. Let's solve it in the following method. It's clear that if we knew the value of
row_switched[0], we would then know the values of the wholecolumn_switched[]array, because they're unambiguously deduced by the equations, in whichrow_switched[0]takes part. Then it's easy to deduce value of every row as well.But we have only two variants for
row_switched[0]: 0 and 1. Let's try each of them (SEE NOTE BELOW), and for each, calculate both arrays! Then we should check that all the equations hold and choose one of two sets that satisfies the whole system and has less switches.If neither satisfies it, then, well, it's unsolvable. Try to solve this one, heh:
This completes the solution. I hope you'll do a +1 just for trying. :)
On the question why this is the least possible number of switches. Indeed, any valid number of switches should satisfy the system of equations outlined above (with 0 and 1 as constraints for values). But that system has not more than two solutions, and we find them all in the algorithm above. So, the algorithm above surely finds the minimal one.
NOTE:
It seems to me, that we can only try one of set. If one passes the system, the other should pass as well. One set is a negation of another, so we just choose the set with less switch number. Sum of switches is 2N. But this only seems and is less clear than the other part.
让我再次解释我的答案的结尾 如何通过行和列切换进行矩阵转换？。
如果可能的话，我们已经通过切换将矩阵转换为零矩阵的问题减少了。首先要注意的是，如果我们想要一个最小的答案，我们永远不会多次切换行或列，因为切换行/列两次与不切换是一样的——这是恒等式的结果（P XOR 1) XOR 1 = P。
让我们看看第一行。第一行中的每个 1 都必须切换为 0。我们可以通过将第一行中的每一列切换为 1 来实现这一点，或者我们可以切换第一行，交换 1 和 0，并且然后将每个新的 1 切换回 0。并且（假设没有切换对）这些是导致第一行减少为全 0 的唯一两组操作。
此时，查看其他行。如果任何行混合有 0 或 1，那么问题就解决了；如果没有列切换，就无法使该行全为 0，这会破坏第一行中的 0。 OTOH，如果每隔一行都是全 0 或全 1，那么您就只剩下行切换了。
最后一步是因为存在 2N 种可能的切换，并且两种解决方案中都不会出现切换。从上面的列切换中应该可以立即清楚这一点；对于行切换，请注意，在一组列切换后全为 0 的行将在另一组列切换后全为 1。因此，在计算一组 K 个切换后，另一组的大小将是 2N - K 个切换。
Let me take another shot at explaining the end of my answer back in How to do matrix conversions by row and columns toggles?.
We've reduced the problem to converting a matrix to the zero matrix via toggles, if possible. Start by noting that, if we want a minimal answer, we'll never toggle a row or column more than once, since toggling a row/column twice is the same as not toggling to begin with -- a consequence of the identity (P XOR 1) XOR 1 = P.
Let's look at the first row. Every 1 in the first row must be toggled to 0. We can do that by toggling each column with a 1 in the first row, or we can toggle the first row, swapping the 1's and 0's, and then toggle each new 1 back to a 0. And (assuming no toggle pairs) those are the only two sets of operations that result in the first row being reduced to all 0's.
At this point, look at the other rows. If any row has a mixture of 0's or 1's, you're done and the problem is insoluble; there is no way to make the row all 0's without a column toggle, and that destroys a 0 in the first row. OTOH, if every other row is all 0's or all 1's, then you just have row toggles remaining.
The final step is a consequence of the fact that there are 2N possible toggles, and no toggle will be part of both solutions. That should be immediately clear from the above for column toggles; for row toggles, note that a row that is all 0's after one set of column toggles will be all 1's after the other set of column toggles. So, after computing one set of K toggles, the size of the other set will be 2N - K toggles.