Find all submatrices of a given matrix

Question

I need to find all possible submatrices of a given mxn matrix. I am trying to do this in python and don't want to use numpy. Can we only do this with loops?

For example: 2x2 matrix

Matrix = [ [1, 2], [3, 4] ] Submatrices =[ [1], [1,2], [2], [3], [4], [3, 4], [[1], [3]], [[2],[4]], [[1,2],[3,4]] ] 

Answer 1

Assuming the matrix

 Matrix = [ [1, 2,3], [3, 4,5], [5,6,7] ] 

Divide into 3 functions:

 def ContinSubSeq(lst): size=len(lst) for start in range(size): for end in range(start+1,size+1): yield (start,end) def getsubmat(mat,start_row,end_row,start_col,end_col): return [i[start_col:end_col] for i in mat[start_row:end_row] ] def get_all_sub_mat(mat): rows = len(mat) cols = len(mat[0]) for start_row,end_row in ContinSubSeq(list(range(rows))): for start_col,end_col in ContinSubSeq(list(range(cols))): yield getsubmat(mat,start_row,end_row,start_col,end_col) 

Run this

 for i in get_all_sub_mat(Matrix): print i 

Or simpler, put in one function:

 def get_all_sub_mat(mat): rows = len(mat) cols = len(mat[0]) def ContinSubSeq(lst): size=len(lst) for start in range(size): for end in range(start+1,size+1): yield (start,end) for start_row,end_row in ContinSubSeq(list(range(rows))): for start_col,end_col in ContinSubSeq(list(range(cols))): yield [i[start_col:end_col] for i in mat[start_row:end_row] ] 

Answer 2

I made a function to extract a matrix from a matrix, and I use to extract all possible combinations, you will find a script, this script solves your problem

 def extract(mat, n, n1, m, m1): l=[] for i in range(n-1, n1): r=[] for j in range(m-1, m1): if mat[i][j] != []: r.append(mat[i][j]) l.append(r) return l # set 1 in i1 and j1 # set dimension+1 in i2 and j2 res = [] for i1 in range(1, 3): for i2 in range(1,3): for j1 in range(1, 3): for j2 in range(1, 3): li= extract(mat, i1,i2,j1,j2) if li !=[] and i2 >= i1 and j2>=j1 : res.append(li) print res 

Answer 3

 def all_sub(r, c, mat): # returns all sub matrices of order r * c in mat arr_of_subs = [] if (r == len(mat)) and (c == len(mat[0])): arr_of_subs.append(mat) return arr_of_subs for i in range(len(mat) - r + 1): for j in range(len(mat[0]) - c + 1): temp_mat = [] for ki in range(i, r + i): temp_row = [] for kj in range(j, c + j): temp_row.append(mat[ki][kj]) temp_mat.append(temp_row) arr_of_subs.append(temp_mat) return arr_of_subs