0

给定一个 NxN 方阵，我想通过删除相等数量的行和列来确定所有可能的方子矩阵。

为了确定所有可能的 2x2 矩阵，我需要循环 4 次。同样，对于 3x3 矩阵，我需要循环 6 次，依此类推。有没有办法在 C++ 中生成代码，以便动态生成循环代码？我已经检查了一些与 C++ 中的代码生成相关的答案，但其中大多数都使用了 python。我对python一无所知。那么，是否可以编写代码以在 C++ 中生成代码？

4

1 回答 1

1

如果我明白你在说什么，你的意思是你需要 M 循环来选择 M 行，M 循环用于 M x M 子矩阵的 M 列，1 <= M <= N

您不需要 2*M 循环来执行此操作。无需使用不断增加的循环数来动态生成代码！

本质上，您需要“组合” i_{1}, i_{2}, ..., i_{M} 和 j_{1}, j_{2}, ..., j_{M} 这样的所有可能组合那 1 <= i_{1} < i_{2} < ... < i_{M} <= N （对于 j 也是如此）

如果你有所有这些 i_{1}, ..., i_{M} 的所有可能组合，你基本上就完成了。

例如，假设您正在使用 10 x 10 矩阵并且需要 4 x 4 子矩阵。

假设您最初选择了行 {1, 2, 3, 4} 和列 {1, 2, 3, 4}。接下来选择列 {1, 2, 3, 5}。接下来 {1, 2, 3, 6} 等等直到 {1, 2, 3, 10}。接下来选择 {1, 2, 4, 5}，下一个 {1, 2, 4, 6} 依此类推，直到达到 {7, 8, 9, 10}。这是您可以按顺序生成所有（“10 选择 4”）组合的一种方式。

继续，编写一个生成这个序列的函数，你就完成了。它可以将 M、N、当前组合（作为 M 值的数组）作为输入并返回下一个组合。

您需要调用此序列来选择下一行和下一列。

我说得有点松散。如果有不清楚的地方，我可以编辑以更新我的答案。

编辑：

我将假设循环索引从 0 开始（C++ 方式！）。为了进一步阐述算法，给定一个组合作为输入，下一个组合可以通过将组合视为排序的“计数器”来生成（除了没有数字重复）。

免责声明：我尚未运行或测试以下代码片段。但是这个想法是给你看的。另外，我不再使用 C++。容忍我的任何错误。

// Requires M <= N as input, (N as in N x N matrix)
void nextCombination( int *currentCombination, int M, int N ) {
    int *arr = currentCombination;
    for( int i = M - 1; i >= 0; i-- ) {
        if( arr[i] < N - M + i ) {
            arr[i]++;
            for( i = i + 1, i < M; i++ ) {
                arr[i] = arr[i - 1] + 1;
            }
            break;
        }
    }

}

// Write code for Initialization: arr = [0, 1, 2, 3]
nextCombination( arr, 4, 10 );
// arr = [0, 1, 2, 4]

// You can check if the last combination has been reached by checking if arr[0] == N - M + 1. Please incorporate that into the function if you wish.

编辑：

实际上我想检查所有可能的子矩阵的奇异性。我的方法是计算所有子矩阵，然后找到它们的行列式。在计算 2x2 矩阵的行列式之后，我将存储它们并在计算 3x3 矩阵的行列式时使用它们。等等。你能建议我一个更好的方法吗？我没有空间和时间的限制。– 藤蔓

使用您建议的直接方法是根据构成子矩阵的行列组合来索引行列式。首先在哈希图中存储 1 x 1 子矩阵的行列式（基本上是条目本身）。

所以对于 10 x 10 的情况，哈希图看起来像这样
{ "0-0" : arr_{0, 0}, "0-1" : arr_{0, 1}, . . . "1-0" : arr_{1, 0}, "1-1" : arr_{1, 1}, . . . "9-9" : arr_{9, 9} }

当 M = 2 时，您可以使用通常的公式计算行列式（已初始化 1 x 1 子矩阵的行列式），然后添加到哈希图中。2 x 2 子矩阵的哈希字符串类似于1:3-2:8原始 10 x 10 矩阵中的行索引为 1,3，列索引为 2, 8。通常，对于 mxm 子矩阵，行列式可以是通过查找所有必要的（已经）计算的 (m - 1) x (m - 1) 行列式来确定 - 这是一个简单的哈希映射查找。再次，计算后将行列式添加到哈希映射中。

当然，您可能需要稍微修改 nextCombination() 函数 - 它当前假定行和列索引从 0 运行到 N - 1。

另一方面，由于要从 1 x 1 开始处理所有子矩阵，因此您不需要 nextCombination() 函数之类的东西。给定一个 2 x 2 矩阵，您只需要多选择一行和一列即可形成一个 3 x 3 矩阵。因此，您需要选择一个行索引（这不是构成 2 x 2 子矩阵的行索引的一部分）和一个类似的列索引。但是对每个 2 x 2 矩阵执行此操作会生成重复的 3 x 3 矩阵 - 您需要考虑一些消除重复的方法。避免重复的一种方法是仅选择索引大于子矩阵中最高行/列索引的行/列。

我再次松散地定义了这个想法。你可以建立在它之上。

于 2016-06-15T17:25:33.157 回答