Задача с умножением матриц по формуле Глинна для расчета перманента

Question

Я пытаюсь реализовать в C ++ вычисление перманента матрицы по формуле Глинна .

Я пытаюсь кратко объяснить, как работает эта формула. Предположим, у нас есть матрица nxn.

| a b c |
| d e f | 
| g h i |

Чтобы вычислить перманент по формуле Глинна, я должен попытаться выполнить «вид» матричного произведения с матрицей, представляющей собой таблицу истинностей длины 2^n с n/2 строками и n столбцами.

Примерно так. Предположим, матрица с n = 3.

| a b c | |+ + +|
| d e f | |+ - +|
| g h i | |+ + -|
          |+ - -|

разработка формулы. Я должен получить:

∆(a + b + c)(d + e + f)(g + h + i)

где:

∆ è равно произведению первой матрицы знака (следовательно, + * + * + = +). Положительный знак a, b и c Я получил его, умножив первый столбец матрицы букв на знак первой строки матрицы знака.

Порядок следующий: умножить первый столбец матрицы A для первой строки матрицы знаков, умножить второй столбец матрицы A для первой строки матрицы знаков и затем умножить последний столбец матрицы A для первой строки матрицы знаков.

Это первый шаг. Вторым будет умножение первого столбца матрицы A для второй строки матрицы знаков, умножение второго столбца матрицы A для второй строки матрицы знаков и затем умножение третьего столбца матрицы A для второго ряд знаков матрицы и т. д.

Конечный результат таков:

= + (a + b + c)(d + e + f)(g + h + i) 
  - (a - b + c)(d - e + f)(g - h + i) 
  - (a + b - c)(d + e - f)(g + h - i)
  + (a - b - c)(d - e - f)(g - h - i)

Я пытаюсь реализовать этот алгоритм в C. Я правильно создал случайную матрицу nxn и матрицу знаков, которые я закодировал таким образом, чтобы выполнить умножения простым способом (+ = 1 и - = -1). Итак, продукт, который я должен сделать, это:

| a b c | |1  1  1|
| d e f | |1 -1  1|
| g h i | |1  1 -1|
          |1 -1 -1|

Функция, которую я пытался создать для запуска этих продуктов и этих сумм:

double permanent(double input_matrix[n][n], int sign_matrix[][n]){

int rows =  pow (2, n) ;
int partial_result = 0;
int result = 1;

for(int r = 0; r < n; r++)
{
   for(int c = 0; c < n; c++)
   {
      partial = partial + input_matrix[c][r] * sign_matrix[r][c];
      //cout << parziale <<  endl;
   }

   cout << partial << endl;
   partial_result = partial_result * parziale;
   partial = 0;

}

Проблема в том, что когда я выполняю partial = partial + input_matrix [c][r] * sign_matrix [r][c];, я не могу "удерживать линию матрицы знаков устойчивой, потому что произведение неверно, потому что я умножаю первый столбец матрицы A на первый ряд Матрица знаков (справа). Вторая строка матрицы знаков (неправильно! Я также должен умножить второй столбец для первой строки матрицы знаков, как в письменной формуле).

Есть предложения?

Answer 1

Я думаю, что вам действительно нужно дважды проверить свое понимание уравнения. Помните, что каждое суммирование или умножение является циклом for. Итак, используя обозначения в оригинальной бумаге , вы получите следующее:

#include <vector>
#include <cassert>

using mat = std::vector<std::vector<double>>;

double permanent(const mat& input_matrix, const mat& sign_matrix)
{
    int m = input_matrix.size();
    assert(m > 2);
    assert(input_matrix[0].size() == m);
    assert(sign_matrix.size() == m);
    int cols = sign_matrix[0].size();
    assert(cols == 1 << (m - 1));

    double result = 0;
    for (int t = 0; t < cols; ++t) {
        double delta = 1;
        for (int k = 0; k < m; ++k) {
            delta *= sign_matrix[k][t];
        }
        double p = 1;
        for (int j = 0; j < m; j++) {
            double s = 0;
            for (int i = 0; i < m; i++) {
                s += sign_matrix[i][t] * input_matrix[i][j];
            }
            p *= s;
        }
        result += delta * p;
    }
    return result / cols;
}

int main()
{
    mat A = { 
        { 1, 4, 7, }, 
        { 2, 5, 8, }, 
        { 3, 6, 9, },
    };
    mat sign_mat = {
        { 1,  1,  1,  1, },
        { 1, -1,  1, -1, },
        { 1,  1, -1, -1, },
    };
    auto perA = permanent(A, sign_mat);
}