通过切换行和列将二进制矩阵转换为 0? [英] Converting a binary matrix to 0s by toggling rows and columns?

问题描述

假设您有一个由 0 和 1 组成的网格.您的目标是通过执行一系列翻转"操作将网格变成全为零的网格:如果翻转网格中的位置 (x, y)，则与 (x, y) 被翻转.

Suppose that you're given a grid of 0s and 1s. Your goal is to turn the grid into a grid of all zeros by performing a series of "flip" operations: if you flip position (x, y) in the grid, then all of the bits in the same row or column as (x, y) get flipped.

有谁知道可以用来解决这个问题的有效算法吗?

Does anyone know of an efficient algorithm that can be used to solve this problem?

推荐答案

解决此问题的一种可能方法是将此问题视为 线性方程组，除了仅使用 0 和 1 而不是实数.

One possible way to solve this is to treat this problem as a linear system of equations, except using just 0 and 1 instead of real numbers.

数字 0 和 1 在 XOR 和 AND 运算下形成字段(顺便说一下，这个字段被称为 GF(2)).也就是说，您可以通过将两个位相加"在一起，将它们相加"在一起，并且您可以通过对它们进行与"运算来将两个位相乘"在一起.事实证明，XOR 和 AND 的行为与正常乘法和加法的许多属性相匹配——例如，乘法和加法是可交换和结合的，乘法分布在加法上.事实证明，这些属性足以让您使用高斯消元来求解线性方程组超过 0 和 1.例如，可以使用高斯消元法来求解这个线性方程组:

The numbers 0 and 1 form a field under the operations XOR and AND (this field is called GF(2), by the way). That is, you can "add" two bits together by XOR-ing them together, and you can "multiply" two bits together by ANDing them. It turns out that the behavior of XOR and AND matches many properties of normal multiplication and addition - multiplication and addition are commutative and associative, and multiplication distributes over addition, for example. It turns out that these properties are sufficient to let you use Gaussian elimination to solve a linear system of equations over 0s and 1s. For example, Gaussian elimination can be used to solve this linear system of equations:

x XOR z = 1
x XOR y XOR z = 0
y XOR z = 0

因此，如果我们可以用使用 XOR 和 AND 的线性方程组来表述您的问题，那么您只需在该字段上使用标准高斯消元法就可以在多项式时间内解决问题.

Consequently, if we can phrase your problem in terms of a linear system of equations using XORs and ANDs, then you can solve the problem in polynomial time by just using standard Gaussian elimination over this field.

要做到这一点，首先要注意反转一位相当于用 1 对其进行异或运算:

To do this, first notice that inverting a bit is equivalent to XOR-ing it with 1:

• 0 异或 1 = 1
• 1 异或 1 = 0

这意味着，如果您切换整个行和列，则相当于将该行和列中的所有内容与值 1 进行异或.

This means that if you toggle an entire row and column, it's equivalent to XORing everything in that row and column with the value 1.

现在，假设你有一个 m ×n 0 和 1 的矩阵.我们将用 A[i][j] 表示第 i 行第 j 列中数字的值.由于切换 (i, j) 会切换同一行和列中的所有元素，因此您可以想象切换 (i, j) 等效于将原始矩阵 A 与新矩阵 A 进行异或，如下所示:

Now, suppose that you have an m × n matrix of 0s and 1s. We'll denote by A[i][j] the value of the number in the ith row and the jth column. Since toggling (i, j) toggles all of the elements in the same row and column, you can imaging that toggling (i, j) is equivalent to XORing the original matrix A to a new matrix A that looks like this:

0 0 ... 0 1 0 ... 0
0 0 ... 0 1 0 ... 0
        ...
0 0 ... 0 1 0 ... 0
1 1 ... 1 1 1 ... 1
0 0 ... 0 1 0 ... 0
        ...
0 0 ... 0 1 0 ... 0
0 0 ... 0 1 0 ... 0

这里，1 在第 i 行和第 j 列，0 在其他地方.

Here, the 1s are in row i and column j, and the 0s are everywhere else.

请注意，网格中的每个位置都会产生这些切换矩阵"之一，因此执行翻转(i，j)"操作的效果是将当前矩阵与切换矩阵编号(i，j).

Note that every position in the grid gives rise to one of these "toggle matrices" such that the effect of performing operation "flip (i, j)" is XOR-ing the current matrix with toggle matrix number (i, j).

现在进行另一个关键观察:对于这个问题，没有最佳解决方案(操作次数最少的解决方案)将同一位置翻转两次.这样做的原因是 XOR 将自身反转:a XOR a = 0.因此，可以通过去除两个翻转来获得更短的解决方案来缩短任何将同一位置翻转两次的解决方案.此外，由于 XOR 是 associative 和 commutative ((x XOR y) XOR z = x XOR (y XOR z), and x XOR y = y XOR x)，不管什么顺序我们执行翻转以获得最佳解决方案.一旦您知道要执行哪些翻转，您所要做的就是按照您喜欢的任何顺序执行翻转.

Now for another key observation: no optimal solution (one with the shortest number of operations) to this problem ever flips the same position twice. The reason for this is that XOR inverts itself: a XOR a = 0. Consequently, any solution that flips the same position twice can be shortened by removing two of the flips to get a shorter solution. Moreover, since XOR is associative and commutative ((x XOR y) XOR z = x XOR (y XOR z), and x XOR y = y XOR x), it doesn't matter what order we perform the flips in for an optimal solution. All you have to do is perform the flips in whatever order you'd like, once you know which flips to do.

将所有这些结合在一起，我们试图确定对于每个可能的翻转，我们是否应该执行该翻转.订购和数量无关紧要.

Combining all this together, we have that we are trying to determine, for each possible flip, whether or not we should perform that flip. Ordering and quantity don't matter.

这是我们了解实际线性方程组的地方.我们得到了一个起始矩阵 A 和一堆不同的切换矩阵"，我们可以做的每个不同的翻转都有一个.让我们用 T[i, j] 表示位置 (i, j) 的切换矩阵.然后我们将引入新变量 b[i, j] 为 0 或 1 值，指示我们是否应该实际翻转位置 (i, j).鉴于此设置，我们正在寻找 b[i, j] 的一组值，使得

Here's where we get to actual linear systems of equations. We're given a starting matrix A and a bunch of different "toggle matrices", one for each of the different flips we can do. Let's denote the toggle matrix for position (i, j) by T[i, j]. We'll then introduce new variables b[i, j] to be a 0 or 1 value indicating whether or not we are supposed to actually flip position (i, j). Given this setup, we are looking for a set of values for the b[i, j]'s such that

A XOR b[1, 1]T[1, 1] XOR b[1, 2]T[1, 2] XOR ... XOR b[m, n]T[m, n] = 0

A XOR b[1, 1]T[1, 1] XOR b[1, 2]T[1, 2] XOR ... XOR b[m, n]T[m, n] = 0

其中 0 是零矩阵.如果可以找到可行的 b 选项，那么您就有了解决方案.如果不是，则不存在解决方案.现在的问题是如何找到它们.

Where 0 is the zero matrix. If it's possible to find a choice of b's that works, then you have your solution. If not, then no solution exists. The question now is how to find them.

为此，我们将对上述系统进行一个小改动.让我们用 A 对这个等式的两边进行异或.由于 A XOR A = 0，这就抵消了左边的 A.由于 A XOR 0 = A，这会将 A 移到右侧.现在我们有

To do this, we'll make one small change to the above system. Let's XOR both sides of this equation by A. Since A XOR A = 0, this cancels out the A from the left side. Since A XOR 0 = A, this moves the A to the right side. Now we have

b[1, 1]T[1, 1] XOR b[1, 2]T[1, 2] XOR ... XOR b[m, n]T[m, n] = A

b[1, 1]T[1, 1] XOR b[1, 2]T[1, 2] XOR ... XOR b[m, n]T[m, n] = A

最后，我们将再做一项更改.我们不将 A 和 T[i, j] 表示为矩阵，而是将它们表示为按行优先顺序的列向量.这意味着上述线性方程组实际上可以不是矩阵之和，而是列向量之和.

Finally, we'll do one more change. Rather than representing A and the T[i, j]'s as matrices, let's represent them as column vectors in row-major order. This means that the above linear system of equations can actually be thought of not as a sum of matrices, but as a sum of column vectors.

为了达成交易，让我们定义一个矩阵 T，其中 T 的第一列是 T[1, 1]，T 的第二列是 T[1, 2]，...，第 mnT 的列是 T[m, n].然后，让我们让 b = (b[1, 1], b[1, 2], ..., b[m, n])^T(顺便说一下，这是一个转置).在这种情况下，我们可以将上述系统改写为

To seal the deal, let's define a matrix T, where the first column of T is T[1, 1], the second column of T is T[1, 2], ..., and the mn-th column of T is T[m, n]. Then, let's let b = (b[1, 1], b[1, 2], ..., b[m, n])^T (that's a transpose, by the way). In that case, we can rewrite the above system as

Tb = A

这太美了！我们现在正在尝试求解向量 b，使得 T 乘以 b 得到矩阵 A.如上所述，由于 0 和 1 与 XOR 和 AND 形成一个域，因此您可以使用标准高斯消元法来求解该系统.

This is beautiful! We're now trying to solve for a vector b such that T multiplied by b gives the matrix A. As mentioned above, since 0s and 1s with XORs and ANDs forms a field, you can use standard Gaussian elimination to solve this system.

那么它的效率如何?那么，矩阵 T 的大小为 mn ×锰因此，在其上运行高斯消元将花费 O(m³n³)，这很大，但对于相当小的网格来说仍然不算太糟糕.我们也可以通过简单地找出哪些条目被切换来在 O(m²n²) 时间内构建网格.总的来说，这为您的问题提供了 O(m³n³) 算法.耶！

So how efficient is this? Well, the matrix T has size mn × mn. Therefore, running Gaussian elimination on it will take time O(m³n³), which is large but still not too bad for reasonably small grids. We can construct the grid in time O(m²n²) as well by simply figuring out what entries get toggled. Overall, this gives an O(m³n³) algorithm for your problem. Yay!

我有一个求解器的实现，用于Lights Out"游戏，这与这个问题极其相似，不同之处在于切换仅翻转 (i, j) 附近的灯，而不是翻转整个行和列.它基于完全相同的方法，因此如果您想使用代码并将其用作起点，您可能可以在短时间内编写此求解器.我已经尝试在代码的相关部分添加注释以使其易于阅读，因此希望它有用.

I have an implementation of a solver for the game "Lights Out", which is extremely similar to this problem except that a toggle only flips the lights in the immediate neighborhood of (i, j), rather than flipping the entire row and column. It is based on the exact same approach, so if you wanted to take the code and use it as a starting point, you could probably code up this solver in a short amount of time. I've tried to add comments to the relevant parts of the code to make it easy to read, so hopefully it's useful.

希望这有帮助！

这篇关于通过切换行和列将二进制矩阵转换为 0?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！