寻找给定矩阵的所有子矩阵。

Question

我需要找到一个给定的mxn矩阵的所有可能的子矩阵。我正在尝试使用Python完成这个操作，但不想使用numpy。我们能否仅使用循环来实现这一点？

例如：2x2矩阵

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

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

- pankajg

---

一个3x3的矩阵怎么样？移除一组随机列仍然被认为是子矩阵吗？或者应该将矩阵的连续部分视为适当的子矩阵？ - ssm

我认为你需要实现两个函数：Combination(x,n)和SubMatrix(x_start,x_end,y_start,y_end)。并且它应该被解决。 - Chiron

@ssm 矩阵的连续部分应被视为一个合适的子矩阵。 - pankajg

Answer 1

假设有一个矩阵。

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

拆分为3个函数：

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)

运行这个

for i in get_all_sub_mat(Matrix):
  print i

或者更简单地说，放入一个函数中：

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

- Chiron

---

谢谢你的努力，但是函数没有返回所有的矩阵。如果我在[[1,2],[2,3]]上尝试，只会返回[[1]]。 - pankajg

@pankajg 在 ContinSubSeq 中漏掉了一个 +1，已经更正。现在请再试一次。 - Chiron

@Chiron 这段代码按预期工作。太棒了。但是你能否用算法步骤来解释一下？我不太理解 yield。 - Karthik

@Karthik，这个想法是枚举所有可能的（StartRow，EndRow）和（StartCol，EndCol）对。然后按行和列切割mat。 “Yield”与返回Array []相同，但速度更快。你可以把“yield”看作是“扔出”。 - Chiron

Answer 2

我编写了一个函数，可以从矩阵中提取矩阵，并用它来提取所有可能的组合。您可以在脚本中找到它，这个脚本可以解决您的问题。

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

- khelili miliana

Answer 3

def printMatrix(arr,r1,c1,r2,c2):
  for i in range(r1,r2+1):
    for j in range(c1,c2+1):
      print(arr[i][j], end=" ")
    print()
      
def allSubmatrix(arr):
  m,n = len(arr), len(arr[0])
  for r1 in range(m):
    for c1 in range(n):
      for r2 in range(r1,m):
        for c2 in range(c1,n):
          printMatrix(arr,r1,c1,r2,c2)  # you can do anything with your submatrix here
          print()

- Aagam Vadecha

Answer 4

不使用函数...

m = [[1,2,3,4],[2,3,4,5],[3,4,5,6]]
r = 3
c = 4

x = 0
while x < r:
    y = x+1
    while y <= r:
        a = 0
        while a < c:
            b = a+1
            while b <= c:
                sm = []
                for i in m[x:y]:
                    sm.append(i[a:b])
                print(sm)
                count += 1
                b += 1
            a += 1
        y += 1
    x += 1

- Krish4

---

欢迎来到SO。目前为止，您的答案还不够充分。请避免发布仅包含代码的答案。尽管您可能没有问题理解代码，但其他人可能会遇到困难。请添加一些解释。此外，请查看初学者指南，它非常好，并且您可以获得成就：提问，获取答案，无干扰。 - Korashen

Answer 5

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

- darshanr