在给定约束下有效枚举所有可能的矩阵

Question

背景

假设我们有一个矩阵族

M

，其大小为

n

逐

n

，应满足以下要求：

1. 矩阵的条目是

   0

   或

   1

   ，即布尔值，但对角线条目始终是

   0

   s
2. 矩阵是对称的，即

   M == t(M)

3. 存在恒定行总和约束

   p

   ，使得

   all(rowSums(M)==p) == TRUE

问题

• 特定的矩阵结构是否有任何潜在的特征可以让我们从中受益以提高搜索效率？
• 看来这个问题可以用图论的方式来解释。例如，该矩阵是由

  n

  个顶点组成的图的邻接矩阵，其入度和出度都等于

  p

  。这可以通过

  sample_degseq

  来完成，但是我们可能必须找到它的所有同构映射。我们怎样才能做到这一点？

到目前为止，我的代码如下所示，但是当我们有较大的

n

或

p

时，速度很慢（而且我不确定在枚举过程中是否遗漏了一些矩阵）。

f <- function(n, p) {
    # helper function to check if requirement holds
    checker <- function(M, p, i = nrow(M) - 1) {
        rs <- rowSums(M)
        if ((i == nrow(M) - 1)) {
            return(all(rs == p))
        } else {
            return(all(rs[1:i] == p) && all(rs[-(1:i)] <= p))
        }
    }

    # start from all-0's matrix
    lst <- list(matrix(0, n, n))
    for (i in 1:(n - 1)) {
        js <- (i + 1):n
        r <- list()
        for (mat in lst) {
            k <- p - sum(mat[i, ])
            if (k == 0) {
                if (checker(mat, p, i)) {
                    r <- c(r, list(mat))
                }
            }
            if (k > 0 && length(js) >= k) {
                idx <- combn(length(js), k, \(v) js[v], simplify = FALSE)
                for (u in idx) {
                    mm <- mat
                    mm[i, u] <- 1
                    mm[u, i] <- 1
                    if (checker(mm, p, i)) {
                        r <- c(r, list(mm))
                    }
                }
            }
        }
        lst <- r
    }
    lst
}

---

示例

• 对于

  n <- 4

  和

  p <- 2

  ，我们可以找到3个矩阵

[[1]]
     [,1] [,2] [,3] [,4]
[1,]    0    1    1    0
[2,]    1    0    0    1
[3,]    1    0    0    1
[4,]    0    1    1    0

[[2]]
     [,1] [,2] [,3] [,4]
[1,]    0    1    0    1
[2,]    1    0    1    0
[3,]    0    1    0    1
[4,]    1    0    1    0

[[3]]
     [,1] [,2] [,3] [,4]
[1,]    0    0    1    1
[2,]    0    0    1    1
[3,]    1    1    0    0
[4,]    1    1    0    0

• 对于

  n <- 3

  和

  p <- 2

  ，我们只能找到 1 个矩阵

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

Answer 1

这将生成满足行和列总数约束的 N 个矩阵，不一定是不同的，然后将其过滤到满足其他约束的矩阵，然后将其减少到唯一的矩阵。它不一定会给出所有可能的此类矩阵，但代码很短并且可能足够好。

set.seed(123)
n <- 4
p <- 2
N <- 1000

L <- r2dtable(N, rep(p,n), rep(p,n))
f <- function(x) max(x) == 1 && all(diag(x) == 0) && all(x == t(x))
unique(Filter(f, L))

给予：

[[1]]
     [,1] [,2] [,3] [,4]
[1,]    0    0    1    1
[2,]    0    0    1    1
[3,]    1    1    0    0
[4,]    1    1    0    0

[[2]]
     [,1] [,2] [,3] [,4]
[1,]    0    1    1    0
[2,]    1    0    0    1
[3,]    1    0    0    1
[4,]    0    1    1    0

[[3]]
     [,1] [,2] [,3] [,4]
[1,]    0    1    0    1
[2,]    1    0    1    0
[3,]    0    1    0    1
[4,]    1    0    1    0