Если я понимаю, о чем вы говорите, вы имеете в виду, что вам требуется M циклов для выбора M строк и M циклов для M столбцов для подматрицы M x M, 1 ‹= M ‹= N
Для этого не нужно 2*м петель. Нет необходимости динамически генерировать код с постоянно растущим числом циклов!
По сути, вам нужно «объединить» все возможные комбинации i_{1}, i_{2},..., i_{M} и j_{1}, j_{2},..., j_{M}, такие что 1 ‹= i_{1} ‹ i_{2} ‹ ... ‹ i_{M} ‹= 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++. Потерпите меня за любые ошибки.
// 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.
Редактировать:
На самом деле я хочу проверить сингулярность всех возможных подматриц. Мой подход состоит в том, чтобы вычислить все подматрицы, а затем найти их определители. Однако после вычисления определителя матриц 2x2 я буду хранить их и использовать при вычислении определителей матриц 3x3. И так далее. Можете ли вы предложить мне лучший подход. У меня нет ограничений в пространстве и времени. - винель
Прямой подход с использованием того, что вы предлагаете, состоит в том, чтобы индексировать детерминанты на основе комбинации строк и столбцов, которая составляет подматрицу. Сначала сохраните определители для подматриц 1 x 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 x 10 равны 1,3, а индексы столбцов равны 2, 8. В общем случае для подматрицы m x m определитель может быть определено путем поиска всех необходимых (уже) вычисленных (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 - вам нужно придумать какой-то способ устранить дубликаты. Один из способов избежать дублирования — выбирать только такие строки/столбцы, индекс которых больше, чем самый высокий индекс строки/столбца в подматрице.
Опять же, я свободно определил идею. Вы можете опираться на это.
person
Prashanth Puranik
schedule
15.06.2016
N
станет больше, количество подматриц будет расти экспоненциально. Зачем вам нужны все они? - person polfosol ఠ_ఠ   schedule 15.06.2016