Find all submatrices of a given matrix

Question

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

Eg: 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]
     ]

Split into 3 function:

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 into 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] ]