如何在C中找到矩阵中元素的所有唯一位置集？

Question

对于5×5矩阵，我需要解决以下问题，但为了解释，我将使用一个3×3矩阵的示例：

A = { { 1, 3, 2 }
     ,{ 3, 2, 3 } 
     ,{ 0, 4, 5 } };

我需要找到所有不同的3个位置集（因为矩阵是3x3），这些位置与其他位置集不共享行或列，计算每个位置集的A元素的总和，并打印这些总和的最小值。

Position = (0,0),(1,1),(2,2) sum = 1+2+5 = 8
           (0,0),(1,2),(2,1) sum = 1+3+4 = 8
           (0,1),(1,0),(2,2) sum = 3+3+5 = 11
           (0,1),(1,2),(2,0) sum = 3+3+0 = 6
           (2,0),(1,1),(0,2) sum = 0+2+2 = 4
           .       
           .       
           .       

（我认为你理解了主要原则）。

所以输出必须包括：（2,0),(1,1),(0,2)最小和=4

记住：我实际上需要对一个5×5矩阵进行计算。

Answer 1

这里还有另一个建议：矩阵中要使用的所有位置集都可以表示为一个单位矩阵的排列，其“1”项告诉您要添加哪些矩阵元素。然后取所有排列的和集合的最小值。您可以使用简单数组表示置换，因为在NxN单位矩阵的置换中只有N个元素等于1。所以调用数组p，其中p（i）告诉您要使用第i行上的哪一列。

这里的基本观察结果是，你需要NxN单位矩阵的所有置换，你可以把它们表示为（0,1，…，N-1）的置换。

伪代码可能如下所示：

Given: an NxN matrix (2-D array), M, for which you want the minimal sum of N
       elements with no subset falling on the same row or column

minsum = N * max entry in M (just initialized to guarantee >= min sum sought)
foreach permutation p of (0,1,...,N-1):
   sum = 0
   for i = 0:N-1:
      sum += M(i,p(i))
      if sum >= minsum: break; # (if we already know this isn't a new min, move on)
   if sum < minsum: minsum = sum
print("minimum sum = ", minsum)

添加一点代码来记住一组特定的位置，这些位置加起来最小，这是留给读者的练习。注意，只要不是一个新的最小和，就放弃任何排列。

对于NxN阵列，有N个！置换，所以在实践中，对于大N（不是您当前的问题，在N=5）来说，这会很快变得昂贵。在这一点上，更深入的动态规划技术——在部分结果出现时尽早退出，或者通过使用（比如）记忆来避免重新计算子集和——将是适用和可取的。

大多数其他算法将以某种方式做同样的基本工作，这些工作在代码中可能看起来很相似，也可能看起来不太相似。我喜欢这种方法，因为它有一个很好的映射到数学术语中相当直接的理解，你可以很容易地发现，随着N的增长，它变得昂贵的原因是需要在快速扩展的排列集合上计算最小值。

计算一个数组的所有置换的算法非常容易获得，并且在C中的函数next_permutation（STL的一部分）中可以免费获得一个。我的建议是谷歌“列出所有排列”，如果您需要使用特定的编程语言，也可以将其添加到查询中。该算法并不十分复杂，并且以递归和迭代形式存在。嘿，对于5x5的情况，你可以静态地列出所有120个排列。

Answer 2

实现这一点的一种功能性方法是使用6个for循环（5个嵌套）。循环从0到2，顶部循环将其迭代#存储在int中（例如称为firstRow）。类似地，第二个循环将存储firstCol。第三个循环将被用来存储第二行，所以如果第二行==firstRow，您需要继续。对于最后两个循环，您需要检查其他两个的indeces。在最内部的嵌套循环中，使用3个坐标对调用findSum函数。

testCoords(*arr1, *arr2, *arr3)
{
    #get the sum
}

#algorithm defined for n = 3 
mySearch(n)
{
    int coord1[2], coord2[2], coord3[2]; #assume 3by3
    int minSum = n * MAX_VAL, obsSum;

    for (int r1 = 0; r1 < n; r1++)
    {
        coord1[0] = r1;

        for (int c1 = 0; c1 < n; c1++)
        {
            coord1[1] = c1;

            for (int r2 = 0; r2 < n; r2++)
            {
                if (r1 != r2)
                {
                    coord2[0] = r2;

                    for (int c2 = 0; c2 < n; c2++)
                    {
                        if (c1 != c2)
                        {
                            coord2[1] = c2;

                            for (int r3 = 0; r3 < n; r3++)
                            {
                                if (r1 != r3 && r2 != r3)
                                {
                                    coord3[0] = r3;

                                    for (int c3 = 0; c3 < n; c3++)
                                    {
                                        coord3[1] = c3;

                                        obsSum = testCoords(coord1, coord2, coord3);
                                        if (obsSum < minSum)
                                        {

                                            minSum = obsSum;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }

}

这对于小数组（如n=3或n=5）来说很好，但是迭代次数很快就变得荒谬，因为它的n^（n*2）。例如，即使使用5x5矩阵，您也会进行1000万迭代（更不用说冗长的算法）。一个更动态的算法或者一个树实现可能是一个很好的选择。例如，递归方法可以找到一个索引对（消除了行和列），然后用结果（n-1）*（n-1）2d数组调用自己，如下所示：

int minSum = n * MAX_VAL;

coordSearch(int **matrix, n)
{
    int thisCoord[2];

    if (n == 1)
    {
        return matrix[0][0];
    }

    else
    {
        for (int i = 0; i < n; i++)
        {
            thisCoord[0] = i;
            for (int j = 0; j < n; j++)
            {
                thisCoord[1] = j;


                ##need to update the matrix s.t. row represented by i is removed and col represented by j is removed
                ##ill leave that up to you -- assume its called updatedMatrix

                updatedMatrix = reduce(matrix, i, j);

                return matrix[thisCoord[0], thisCoord[1]] + coordSearch(updatedMatrix, n-1);
            }
        }
    }
}

int main(void)
{
        #have some 2d structure that is n * n

        int minSum = n * MAX_VAL, obsSum;
        int row, col;

        for (int i = 0; i < n; i++)
        {
            row = i

            for (int j = 0; j < n; j++)
            {
                col = j;

                updatedMatrix = reduce(matrix, row, col);
                obsSum = coordSearch(updatedMatrix, n- 1);
                if (obsSum < minSum)
                {
                    minSum = obsSum;
                }
            }
        }
}

对于一个3x3的2d数组，递归方法将在顶层查看9个坐标对，然后在下一个级别我们将处理一个2x2的2d数组，所以我们将只考虑4个坐标对，然后在底层我们只返回无论哪个值驻留在我们的1x1“二维数组”中。复杂度是n^2*（n-1)^2 * .. * 1。请记住，每个“步骤”都需要更新矩阵，这是一个操作密集的过程。