Znajdź wszystkie submatrices danej matrycy

Question

Potrzebuję znaleźć wszystkie możliwe pod-macierze danej matrycy mxn. Próbuję to zrobić w python i nie chcę używać numpy. Czy możemy to zrobić tylko za pomocą pętli?

Np macierz 2x2

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

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

Answer 1

Zakładając matrycy

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

podzielony na 3 Zastosowanie:

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) 

uruchomić ten

for i in get_all_sub_mat(Matrix): 
    print i 

Albo prościej, umieścić w jednej funkcji:

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

zrobiłem funkcją pozwalają wyodrębnić macierz z matrycy, a ja us'it dla ekstraktu wszelką możliwą combinaison znajdziesz skrypt, ten skrypt rozwiązać swoje 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