Как я могу найти все уникальные наборы позиций элементов в матрице в 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). В этот момент более глубокие методы динамического программирования c, позволяющие досрочно прекратить работу с частичными результатами или избежать повторного вычисления сумм подмножеств с помощью, скажем, запоминания, будут применимы и желательны.

Большинство других алгоритмов собираются сделать то же самое c работает таким образом, что может выглядеть или не выглядеть явно схожим в коде. Мне нравится этот подход, потому что он имеет хорошее отображение в довольно прямолинейном понимании в математических терминах, и вы можете легко определить, что быстро растет с ростом N необходимость в том, чтобы вычислить минимум для быстро расширяющегося набора перестановок .

Алгоритмы для вычисления всех перестановок массива довольно легко найти, и вы получаете их бесплатно в C ++ в функции next_permutation, которая является частью STL. Я рекомендую Google "перечислить все перестановки", и если вам нужно работать на определенном языке программирования, добавьте это и в запрос. Алгоритм не очень сложен и существует как в рекурсивной, так и в итерационной формах. И, эй, для случая 5x5 вы могли бы в любом случае статически перечислить все 120 перестановок.

Answer 2

Функциональный, хотя и наивный, способ сделать это - использовать 6 циклов for (5 вложенных). L oop от 0 до 2 с верхним l oop, хранящим свою итерацию # в int (называемую, например, firstRow). Аналогично второй l oop будет хранить firstCol. Третий l oop будет использоваться для хранения secondRow, поэтому вам нужно continue, если secondRow == firstRow. Для последних двух циклов вам нужно будет сравнить значения с двумя другими. Во внутреннем вложенном l oop вызовите функцию 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 вы будете делать 10 миллионов итераций (не говоря уже о длинном многоточном алгоритме). Более динамический алгоритм c или, возможно, реализация дерева, вероятно, хорошо здесь подходят. Например, рекурсивный подход может найти одну индексную пару (которая исключает строку и столбец), а затем вызывает себя с результирующим (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 «2d массиве». Сложность равна n ^ 2 * (n-1) ^ 2 * .. * 1. Имейте в виду, однако, что каждый «шаг» требует обновления матрицы, которая является процедурой с плотной операцией.