javascript - 如何创建一个由 0 和 1 组成的矩阵，使得行和列之和达到特定值？

Question

我需要生成一个具有 n 列和 m 行的矩阵，其中每个单元格可以是 0 或 1，使得每列中的数字之和等于 c，每行中的数字之和等于 r。如果这是不可能的(可能大多数时候)，它应该将列总和为 c+/-d ，将行总和为 r+/-d ，以便 max(d )行和列)尽可能小。换句话说，行的每个总和应接近于 r，列的每个总和应接近于 c。

为了说明当不存在完美解决方案时我正在寻找什么，这个解决方案:

1.1.1.......
1.1.1.......
...1..1...1.
...1.1..1...
....1...1..1

比这个解决方案更好:

1.1.1.......
1.1.1.......
...1..1...1.
...1.1..1...
....11..1...

因为最后一行的总和为 0(与 1 相比)，而之前的解决方案与所需的行总和 2 相差甚远。

创建一个仅包含行的矩阵很容易 - 使用恰好 r 1s 对向量进行排列。 那么如何满足第二个条件呢？找到总和过高而另一列过低的列并交换一些数字？这会有帮助吗，需要多长时间，是否会终止，如果不可能得到完美的结果，我什么时候停止？有更好的办法吗？

您可以使用伪代码或您选择的语言或只是随机简介。

我找到了Finding if binary matrix exists given the row and column sums其中讨论了回答是否可能，甚至在可能的情况下构建解决方案。如果不可能的话，这样的解决方案将具有非常大的 ds。

还有这篇论文https://www.sciencedirect.com/science/article/pii/S0012365X06003980我不太明白，但它似乎也与构建完美的解决方案有关

Answer 1

这可以通过整数线性规划来完成。

library(lpSolve)

# inputs
nr <- 3  # no of rows
nc <- 3  # no of cols
r <- 2   # sum of each row equals r
c <- 2   # sum of each col equals c

obj <- rep(1, nr * nc)
const.mat <- rbind(
 t(rep(1, nc) %x% diag(nr)),  # this matrix multiplied by c(m) is row sums
 (diag(nc) %x% t(rep(1, nr)))  # this matrix multiplied by c(m) is col sums
)
const.rhs <- c(rep(r, nr), rep(c, nc))
out <- lp(obj = obj, const.mat = const.mat, const.dir = "=", const.rhs = const.rhs, 
  all.bin = TRUE)

out
## Success: the objective function is 6 

matrix(out$solution, nr, nc)
##      [,1] [,2] [,3]
## [1,]    0    1    1
## [2,]    1    0    1
## [3,]    1    1    0