Нахождения всех подматриц
Как перебрать все подматрицы? Подматрицей называется часть матрицы, полученная вычеркиванием какого-либо количества строк, и(или) какого-либо количества столбцов. Для примера матрица:
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
26 27 28 29 30
31 32 33 34 35
Подматрица:
12 13 15
22 23 25
27 28 30
При попытках написать алгоритм получается очень много вложенных циклов. Какой алгоритм можно использовать?
Ответы (1 шт):
Если размер не слишком большой (скажем, до 32x32 :)), обозначим вычеркнутую строку/столбец 0, оставленную - 1. Тогда любой набор вычеркиваний из набора N столбцов описывается числом от 0 до 2N. То же и для строк.
Так что получаем два цикла - по строкам и по столбцам, ну, а внутри надо просто аккуратно разобраться, какие строки и столбцы остаются и записать получающуюся матрицу.
Для показанного вами варианта имеется 1024 подматрицы - от пустой до полной матрицы.