Напечатать минор матрицы определитель которого наибольший

#cpp

В общем у меня есть матрица 4х4 и мне нужно напечатать минор матрицы определитель
которого Наибольший. Пока я знаю как заполнить матрицу рандомно цифрами и найти ее
определитель но проблемы в том, что я не знаю как найти все миноры матрицы. Кто-то
может помочь с кодом? 

#include 
#include  

using std::cin;
using std::cout;

int main(int argc, char const *argv[]) {
    int n; cin >> n;
    int** matrix = new int*[n];
    for (int i = 0; i < n; i ++)
    {
        matrix[i] = new int [n];
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j ++) {
            matrix[i][j] = rand() % 10;
        }
    }
    return 0;
}


Ищу  определитель формулой d = d + (pow(-1 ,c) * mat[0][c] * det(n - 1 ,submat))
    

Ответы

Ответ 1

Лобовое решение данной задачи пугает своей переборностью, но если решать задачу в
лоб, т.е. через вычисление всех возможных миноров (1, то вам понадобится способ перечисления
всех возможных квадратных подматриц. Минор определяется одинаковыми по мощности подмножествами
строк и столбцов матрицы. Вот такие подмножества вам и надо генерировать, во всех возможных
их вариантах.

Например, для каждого возможного подмножества строк мощности 1 надо сгенерировать
все возможные подмножества столбцов мощности 1. Для каждого возможного подмножества
строк мощности 2 надо сгенерировать все возможные подмножества столбцов мощности 2.
И т.д. до мощности n - 1 (2.

Задавать такие подмножества можно парой упорядоченных по возрастанию векторов целых
чисел, т.е. наборами индексов строк и столбцов матрицы. Числа берутся из диапазона
[0, n), а размер вектора задает рассматриваемый в данный момент порядок минора m. Тогда
функция, перечисляющая все возможные подмножества, может выглядеть, например, так

bool next_subset(std::vector &subset, unsigned n)
{
  unsigned overflow = n;
  auto it = subset.end();

  do
  {
    --it;
    if (++*it < overflow || it == subset.begin())
      break;

    --overflow;
  } while (true);

  assert(*it <= overflow);
  if (*it == overflow)
    return false;

  for (++it, ++overflow; it != subset.end(); ++it, ++overflow)
  {
    *it = *(it - 1) + 1;
    assert(*it < overflow);
  }

  return true;
}


В качестве самого первого подмножества используется вектор { 0, 1, ..., m-1 }, а
далее последовательные вызовы этой функции будут генерировать вам всевозможные подмножества
длины m, пока функция не вернет false.

Таким образом, общая структура переборного алгоритма будет такой (2

int main()
{
  unsigned n = 0;
  std::cin >> n;
  // `n` - размер матрицы

  ...

  for (unsigned m = 1; m < n; ++m)
  { // `m` - порядок минора
    std::vector rows(m);
    std::iota(rows.begin(), rows.end(), 0);

    do
    {
      std::vector columns(m);
      std::iota(columns.begin(), columns.end(), 0);

      do
      {
        // А сюда вставляем вычисление определителя для минора
        // образованного строками из `rows` и столбцами из `columns`
        /*
        for (unsigned i : rows) std::cout << i << " ";
        std::cout << "- ";
        for (unsigned i : columns) std::cout << i << " ";
        std::cout << std::endl;
        */

      } while (next_subset(columns, n));
    } while (next_subset(rows, n));
  }
}


Я пока что вставил в "тело" алгоритма отладочную печать, которая продемонстрирует
вам, какие генерируются наборы строк и столбцов минора. 

А дальше - дело техники. Вам надо лишь модифицировать вашу функцию вычисления определителя
так чтобы она работала не напрямую с исходной матрицей, а с "виртуальной" подматрицей,
задаваемой индексными массивами rows и columns.

Или, если вам так больше нравится, вы можете явно формировать отдельную временную
подматрицу из rows и columns и напускать на нее вашу готовую функцию вычисления определителя.



1) Минор - это по определению и есть определитель, т.е. "определитель минора" - это
уже "масло масляное".

2) Диапазон порядков миноров и, соответственно, внешнего цикла будет зависеть от
того, считаете ли вы минором определитель всей матрицы (минор порядка n).



Лирическое отступление: Остроумным "хакерским" способом перечисления всех подмножеств
размера m для данного множества размера n является bit-twiddling техника, основанная
на функции 

unsigned next_combination(unsigned x)
{
  unsigned u = x & -x;
  unsigned v = u + x;
  x = v  + (((v ^ x) / u) >> 2);
  return x;
}


Эта функция перечисляет в порядке возрастания все двоичные числа, содержащие одно
и то же количество единичных битов в своем представлении. Как бы мне ни хотелось, я,
однако, не вижу необходимости притягивать за уши этот подход в решение данной задачи.

Хотя можно заметить, что на тех размерностях, на которых эту задачу имеет смысл решать
перебором, перечисление разнообразных битовых подмножеств для построения подматриц
можно выполнить просто как 

for (unsigned rows = 1; rows < (1u << n) - 1; ++rows)
  for (unsigned columns = 1; columns < (1u << n) - 1; ++columns)
    if (count_bits(rows) == count_bits(columns)) 
    { // Одинаковое количество единичных битов
      // Считаем минор
    }