Определить все квадратные подматрицы данной матрицы NxN в переполнении стека

Если я понимаю, что вы говорите, вы имеете в виду, что вам требуется M циклов для выбора M строк, а M циклов для M столбцов для подматрицы M x M, 1 <= М <= N

Вам не нужны 2 * M петли, чтобы сделать это. Нет необходимости динамически генерировать код с постоянно увеличивающимся числом циклов!

По сути, вам нужно «объединить» все возможные комбинации i_ {1}, i_ {2}, …, i_ {M} и j_ {1}, j_ {2}, …, j_ {M}, таких это 1 <= i_ {1} < I_ {2} < … < я} <= 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.

Редактировать:

На самом деле я хочу проверить особенности всех возможных подматриц. Мой подход состоит в том, чтобы вычислить все подматрицы и затем найти их определители. Однако после вычисления определителя матриц 2×2 я буду хранить их и использовать при вычислении определителей матриц 3×3. И так далее. Можете ли вы предложить мне лучший подход. У меня нет ограничений по пространству и времени. — винель

Прямой подход, использующий то, что вы предлагаете, заключается в индексации детерминантов на основе комбинации строк-столбцов, которая составляет подматрицу. Сначала сохраните определители для 1 х 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 × 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 — вам нужно придумать способ устранения дубликатов. Одним из способов избежать дублирования является выбор только такой строки / столбца, индекс которой больше, чем самый высокий индекс строки / столбца в подматрице.

Опять же, я слабо определил эту идею. Вы можете основываться на этом.