确定是否可以通过翻转矩阵的行和列来达到给定二进制矩阵的算法

Question

我需要帮助找到一种算法，该算法尽可能有效地检查是否可以通过仅翻转矩阵的行和列来达到给定的二进制矩阵。每当你翻转一行或一列时，所有的 0 都变成 1，所有的 1 都变成 0

确定是否可以通过翻转一个矩阵的行和列来达到给定二进制矩阵的算法

例如这个矩阵可以通过翻转第二行然后翻转第二列来实现:

+---+---+---+
| 1 | 0 | 1 |
+---+---+---+
| 0 | 1 | 0 |
+---+---+---+
| 1 | 0 | 1 |
+---+---+---+

但是这个矩阵不能是你做的任何翻转

+---+---+---+
| 1 | 0 | 0 |
+---+---+---+
| 0 | 1 | 0 |
+---+---+---+
| 0 | 0 | 1 |
+---+---+---+

Answer 1

这可以按如下方式进行测试:

取目标矩阵的第一列。所有其他列应该与第一列相同，或者应该相反(翻转)。如果且仅当是这种情况，则可以通过从具有全 1 值的初始矩阵翻转行/列来达到目标​​矩阵。

当然，您也可以对行进行测试，但是对行或列进行测试就足够了。

执行哪些翻转？

如果上述测试为正，您还可以查看可以执行哪些翻转以达到目标矩阵:

在目标矩阵的第一行，识别值为 0 的单元格:这些是您需要在初始矩阵中翻转的列。

在目标矩阵的第一列中，识别值与目标矩阵左上角的值不同的单元格(因此这已经排除了第一个值):那些是您需要在初始矩阵中翻转的行。

执行翻转的顺序并不重要。显然，这只给出了一种解决方案。一般可以有多个。

实现

这是一个简单的 JavaScript 片段，它执行验证并在可能的情况下提供要交换的列和行的列表:

function getFlips(matrix) {
    // Verification
    for (let i = 1; i < matrix.length; i++) {
        let flip = matrix[i][0] ^ matrix[0][0]; // XOR operation
        for (let j = 0; j < matrix[0].length; j++) {
            if (matrix[i][j] ^ flip != matrix[0][j]) return false; // Not possible
        }
    }
    // If we get here, it is possible: determine which rows/columns to flip
    let flips = { rows: [], columns: [] };
    for (let j = 0; j < matrix[0].length; j++) {
        if (matrix[0][j] == 0) flips.columns.push(j+1);
    }
    for (let i = 1; i < matrix.length; i++) {
        if (matrix[i][0] != matrix[0][0]) flips.rows.push(i+1);
    }
    return flips;
}


// I/O management
inp.oninput = function () {
    // Convert input to matrix of numbers
    let matrix = inp.value.split('\n').map(row => Array.from(row, Number));
    // Perform algorithm
    let flips = getFlips(matrix);
    // Output the result in human readable format
    out.textContent = flips 
        ? 'Number(s) of the column(s) to flip: ' 
            + (flips.columns.length ? flips.columns : 'none') + '\n' +
          'Number(s) of the row(s) to flip: ' 
            + (flips.rows.length ? flips.rows : 'none')
        : 'Not possible';
};

inp.oninput();

Enter the values of the matrix:<br>
<textarea id="inp" rows="4" cols="4">101
010
101</textarea><br>
Solution:
<pre id="out"></pre>