r - 寻找具有所有相等元素的最大方子矩阵

Question

有谁知道如何对最大 K 进行子集化，使得 K x K 是一个具有所有相同元素的子矩阵，即，该子矩阵中的所有元素必须与给定的 N x N 矩阵相同？ 我在除 R 之外的其他编程语言中找到了很多示例。如果您知道，我也更喜欢 dplyr。

有其他语言解决方案的链接: https://www.geeksforgeeks.org/maximum-size-sub-matrix-with-all-1s-in-a-binary-matrix/

但是当所有相同的元素彼此相邻时，此链接提供了一种特殊情况。它检索相同元素的最大块，而不是一般的子矩阵。我不想在这种情况下限制子集化。

Answer 1

这是一个基本的 R 实现。

如果想在非方阵内搜索最大方子矩阵，可以试试下面的代码:

r <- list()
for (w in rev(seq(min(dim(M))))) {
  for (rs in seq(nrow(M)-w+1)) {
    for (cs in seq(ncol(M)-w+1)) {
      mat <- M[rs-1+(1:w),cs-1+(1:w)]
      u <- unique(c(mat))
      if (all(u!=0) &length(u)==1) r[[length(r)+1]] <- mat
    }
  }
  if (length(r)>0) break
}

这样

> r
[[1]]
     [,1] [,2]
[1,]    3    3
[2,]    3    3

[[2]]
     [,1] [,2]
[1,]    2    2
[2,]    2    2

[[3]]
     [,1] [,2]
[1,]    3    3
[2,]    3    3

[[4]]
     [,1] [,2]
[1,]    2    2
[2,]    2    2

[[5]]
     [,1] [,2]
[1,]    1    1
[2,]    1    1

[[6]]
     [,1] [,2]
[1,]    1    1
[2,]    1    1

[[7]]
     [,1] [,2]
[1,]    3    3
[2,]    3    3

[[8]]
     [,1] [,2]
[1,]    3    3
[2,]    3    3

数据

M <- structure(c(1L, 3L, 1L, 2L, 1L, 3L, 3L, 2L, 2L, 3L, 3L, 1L, 1L, 
1L, 2L, 2L, 2L, 2L, 3L, 1L, 3L, 1L, 1L, 1L, 1L, 2L, 1L, 1L, 2L, 
2L, 2L, 1L, 3L, 1L, 3L, 2L, 2L, 2L, 2L, 3L, 2L, 1L, 3L, 2L, 1L, 
1L, 3L, 2L, 2L, 3L, 3L, 2L, 2L, 2L, 2L, 1L, 2L, 2L, 2L, 2L, 1L, 
3L, 3L, 2L, 3L, 3L, 2L, 3L, 3L, 1L, 1L, 1L, 1L, 3L, 2L, 3L, 1L, 
1L, 2L, 1L, 1L, 1L, 1L, 3L, 2L, 1L, 1L, 3L, 3L, 3L, 2L, 2L, 2L, 
3L, 2L, 2L, 3L, 3L, 3L, 1L, 2L, 2L, 1L, 3L, 3L, 2L, 3L, 2L, 1L, 
2L, 1L, 3L, 3L, 1L, 2L, 1L, 3L, 2L, 3L, 3L, 1L, 1L, 2L, 2L, 2L, 
1L, 1L, 1L, 2L, 1L, 3L, 2L, 3L, 3L, 2L, 3L, 3L, 1L, 1L, 2L, 2L, 
1L, 2L, 3L, 3L, 3L, 3L, 3L, 1L, 3L), .Dim = c(15L, 10L))

> M
      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
 [1,]    1    2    2    1    1    3    2    2    1     3
 [2,]    3    2    1    3    3    1    2    3    1     3
 [3,]    1    2    3    2    3    1    2    2    2     1
 [4,]    2    3    1    2    2    2    3    1    2     1
 [5,]    1    1    3    3    3    1    2    2    2     2
 [6,]    3    3    2    3    3    1    2    1    1     2
 [7,]    3    1    2    2    2    1    3    3    1     1
 [8,]    2    1    2    2    3    1    3    3    1     2
 [9,]    2    1    2    2    3    3    3    1    2     3
[10,]    3    1    3    2    1    2    1    2    1     3
[11,]    3    2    2    1    1    1    2    1    3     3
[12,]    1    1    1    2    1    1    2    3    2     3
[13,]    1    1    3    2    1    3    1    2    3     3
[14,]    1    2    2    2    3    3    3    3    3     1
[15,]    2    2    1    2    2    3    3    3    2     3

编辑

上述方法在处理大型矩阵时效率低下，因为所有组合都已检查。下面的方法是 https://www.geeksforgeeks.org/maximum-size-sub-matrix-with-all-1s-in-a-binary-matrix/ 中所述算法的 R 实现。 ，效率要高得多。

M <- unname(as.matrix(read.csv(file = "test2.csv")))
S <- matrix(0,nrow = nrow(M),ncol = ncol(M))
S[,1] <- M[,1]
for (i in 1:nrow(S)) {
  for (j in 2:ncol(S)) {
    if (M[i,j]==1) {
      if (i==1) {
        S[i,j] <- M[i,j]
      } else {
        S[i,j] <- min(c(S[i,j-1],S[i-1,j],S[i-1,j-1]))+1
      }
    }
  }
}

inds <- which(S == max(S),arr.ind = TRUE)
w <- seq(max(S))-1
res <- lapply(seq(nrow(inds)), function(k) M[inds[k,"row"]-w,inds[k,"col"]-w])