Backtracking: List all possible matrices with row and column sum constraints
This is a follow-up question of an interesting problem. Briefly speaking, the goal is to produce a random binary matrix, where both the row sum and column sum should satisfy with respective constraints.
A bit different from the goal in the original problem, I would like to obtain a list of ALL possible matrices that meet the requirement, not just a random instance.
I am thinking this kind of constrained problem might be solved using the backtracking algorithm. I tried it by myself but seems its not efficient (I am not happy with it since it's super slow especially when we have longer constraint vectors or many TRUEs to be filled in the matrix. I would like to see backtracking solutions that are more efficient and elegant and learn from them. Thanks!
I created the code below, which searches all possible matrices that meet the row/column sum constraints.
f <- function(rsum, csum) {
# size of desired output matrix
nr <- length(rsum)
nc <- length(csum)
if (sum(rsum)!=sum(csum)) {
stop("Sum of rsum and csum are NOT equal!")
} else {
N <- sum(rsum)
}
# recursion function that searches all possible matrices under rsum/csum constraints
helper <- function(k) {
if (k == 1) {
mat <- matrix(0,nr,nc)
return(lapply(1:(nr*nc+1-N),replace, x = mat, values = 1))
}
lst <- Recall(k - 1)
res <- c()
for (m in lst) {
l <- c(m)
zs <- which(l == 0)
zs <- zs[zs >= max(which(l == 1))]
for (z in zs) {
ll <- matrix(replace(l, z, 1),nr,nc)
if (all(c(rowSums(ll) <= rsum,colSums(ll) <= csum)) && (!list(ll) %in% res)) {
res <- c(res, list(ll))
}
}
}
res
}
# run helper, return a list of all possible matrices
helper(N)
}
When we run the example below
rsum <- c(3, 2, 2, 1)
csum <- c(2, 2, 2, 2)
output <- f(rsum, csum)
we will obtain a list of matrices (of length 48 in this case)
> out
[[1]]
[,1] [,2] [,3] [,4]
[1,] 1 1 1 0
[2,] 1 1 0 0
[3,] 0 0 1 1
[4,] 0 0 0 1
[[2]]
[,1] [,2] [,3] [,4]
[1,] 1 1 0 1
[2,] 1 1 0 0
[3,] 0 0 1 1
[4,] 0 0 1 0
[[3]]
[,1] [,2] [,3] [,4]
[1,] 1 1 1 0
[2,] 1 0 1 0
[3,] 0 1 0 1
[4,] 0 0 0 1
[[4]]
[,1] [,2] [,3] [,4]
[1,] 1 1 1 0
[2,] 1 0 0 1
[3,] 0 1 1 0
[4,] 0 0 0 1
[[5]]
[,1] [,2] [,3] [,4]
[1,] 1 1 1 0
[2,] 1 0 0 1
[3,] 0 1 0 1
[4,] 0 0 1 0
[[6]]
[,1] [,2] [,3] [,4]
[1,] 1 1 0 1
[2,] 1 0 1 0
[3,] 0 1 1 0
[4,] 0 0 0 1
[[7]]
[,1] [,2] [,3] [,4]
[1,] 1 1 0 1
[2,] 1 0 1 0
[3,] 0 1 0 1
[4,] 0 0 1 0
[[8]]
[,1] [,2] [,3] [,4]
[1,] 1 1 0 1
[2,] 1 0 0 1
[3,] 0 1 1 0
[4,] 0 0 1 0
[[9]]
[,1] [,2] [,3] [,4]
[1,] 1 1 1 0
[2,] 1 0 0 1
[3,] 0 0 1 1
[4,] 0 1 0 0
[[10]]
[,1] [,2] [,3] [,4]
[1,] 1 1 0 1
[2,] 1 0 1 0
[3,] 0 0 1 1
[4,] 0 1 0 0
[[11]]
[,1] [,2] [,3] [,4]
[1,] 1 0 1 1
[2,] 1 1 0 0
[3,] 0 1 1 0
[4,] 0 0 0 1
[[12]]
[,1] [,2] [,3] [,4]
[1,] 1 0 1 1
[2,] 1 1 0 0
[3,] 0 1 0 1
[4,] 0 0 1 0
[[13]]
[,1] [,2] [,3] [,4]
[1,] 1 0 1 1
[2,] 1 1 0 0
[3,] 0 0 1 1
[4,] 0 1 0 0
[[14]]
[,1] [,2] [,3] [,4]
[1,] 1 0 1 1
[2,] 1 0 1 0
[3,] 0 1 0 1
[4,] 0 1 0 0
[[15]]
[,1] [,2] [,3] [,4]
[1,] 1 0 1 1
[2,] 1 0 0 1
[3,] 0 1 1 0
[4,] 0 1 0 0
[[16]]
[,1] [,2] [,3] [,4]
[1,] 1 1 1 0
[2,] 0 1 1 0
[3,] 1 0 0 1
[4,] 0 0 0 1
[[17]]
[,1] [,2] [,3] [,4]
[1,] 1 1 1 0
[2,] 0 1 0 1
[3,] 1 0 1 0
[4,] 0 0 0 1
[[18]]
[,1] [,2] [,3] [,4]
[1,] 1 1 1 0
[2,] 0 1 0 1
[3,] 1 0 0 1
[4,] 0 0 1 0
[[19]]
[,1] [,2] [,3] [,4]
[1,] 1 1 0 1
[2,] 0 1 1 0
[3,] 1 0 1 0
[4,] 0 0 0 1
[[20]]
[,1] [,2] [,3] [,4]
[1,] 1 1 0 1
[2,] 0 1 1 0
[3,] 1 0 0 1
[4,] 0 0 1 0
[[21]]
[,1] [,2] [,3] [,4]
[1,] 1 1 0 1
[2,] 0 1 0 1
[3,] 1 0 1 0
[4,] 0 0 1 0
[[22]]
[,1] [,2] [,3] [,4]
[1,] 1 1 1 0
[2,] 0 0 1 1
[3,] 1 1 0 0
[4,] 0 0 0 1
[[23]]
[,1] [,2] [,3] [,4]
[1,] 1 1 0 1
[2,] 0 0 1 1
[3,] 1 1 0 0
[4,] 0 0 1 0
[[24]]
[,1] [,2] [,3] [,4]
[1,] 1 1 1 0
[2,] 0 0 1 1
[3,] 1 0 0 1
[4,] 0 1 0 0
[[25]]
[,1] [,2] [,3] [,4]
[1,] 1 1 0 1
[2,] 0 0 1 1
[3,] 1 0 1 0
[4,] 0 1 0 0
[[26]]
[,1] [,2] [,3] [,4]
[1,] 1 0 1 1
[2,] 0 1 1 0
[3,] 1 1 0 0
[4,] 0 0 0 1
[[27]]
[,1] [,2] [,3] [,4]
[1,] 1 0 1 1
[2,] 0 1 0 1
[3,] 1 1 0 0
[4,] 0 0 1 0
[[28]]
[,1] [,2] [,3] [,4]
[1,] 1 0 1 1
[2,] 0 1 1 0
[3,] 1 0 0 1
[4,] 0 1 0 0
[[29]]
[,1] [,2] [,3] [,4]
[1,] 1 0 1 1
[2,] 0 1 0 1
[3,] 1 0 1 0
[4,] 0 1 0 0
[[30]]
[,1] [,2] [,3] [,4]
[1,] 1 0 1 1
[2,] 0 0 1 1
[3,] 1 1 0 0
[4,] 0 1 0 0
[[31]]
[,1] [,2] [,3] [,4]
[1,] 1 1 1 0
[2,] 0 1 0 1
[3,] 0 0 1 1
[4,] 1 0 0 0
[[32]]
[,1] [,2] [,3] [,4]
[1,] 1 1 0 1
[2,] 0 1 1 0
[3,] 0 0 1 1
[4,] 1 0 0 0
[[33]]
[,1] [,2] [,3] [,4]
[1,] 1 1 1 0
[2,] 0 0 1 1
[3,] 0 1 0 1
[4,] 1 0 0 0
[[34]]
[,1] [,2] [,3] [,4]
[1,] 1 1 0 1
[2,] 0 0 1 1
[3,] 0 1 1 0
[4,] 1 0 0 0
[[35]]
[,1] [,2] [,3] [,4]
[1,] 1 0 1 1
[2,] 0 1 1 0
[3,] 0 1 0 1
[4,] 1 0 0 0
[[36]]
[,1] [,2] [,3] [,4]
[1,] 1 0 1 1
[2,] 0 1 0 1
[3,] 0 1 1 0
[4,] 1 0 0 0
[[37]]
[,1] [,2] [,3] [,4]
[1,] 0 1 1 1
[2,] 1 1 0 0
[3,] 1 0 1 0
[4,] 0 0 0 1
[[38]]
[,1] [,2] [,3] [,4]
[1,] 0 1 1 1
[2,] 1 1 0 0
[3,] 1 0 0 1
[4,] 0 0 1 0
[[39]]
[,1] [,2] [,3] [,4]
[1,] 0 1 1 1
[2,] 1 0 1 0
[3,] 1 1 0 0
[4,] 0 0 0 1
[[40]]
[,1] [,2] [,3] [,4]
[1,] 0 1 1 1
[2,] 1 0 0 1
[3,] 1 1 0 0
[4,] 0 0 1 0
[[41]]
[,1] [,2] [,3] [,4]
[1,] 0 1 1 1
[2,] 1 0 1 0
[3,] 1 0 0 1
[4,] 0 1 0 0
[[42]]
[,1] [,2] [,3] [,4]
[1,] 0 1 1 1
[2,] 1 0 0 1
[3,] 1 0 1 0
[4,] 0 1 0 0
[[43]]
[,1] [,2] [,3] [,4]
[1,] 0 1 1 1
[2,] 1 1 0 0
[3,] 0 0 1 1
[4,] 1 0 0 0
[[44]]
[,1] [,2] [,3] [,4]
[1,] 0 1 1 1
[2,] 1 0 1 0
[3,] 0 1 0 1
[4,] 1 0 0 0
[[45]]
[,1] [,2] [,3] [,4]
[1,] 0 1 1 1
[2,] 1 0 0 1
[3,] 0 1 1 0
[4,] 1 0 0 0
[[46]]
[,1] [,2] [,3] [,4]
[1,] 0 1 1 1
[2,] 0 1 1 0
[3,] 1 0 0 1
[4,] 1 0 0 0
[[47]]
[,1] [,2] [,3] [,4]
[1,] 0 1 1 1
[2,] 0 1 0 1
[3,] 1 0 1 0
[4,] 1 0 0 0
[[48]]
[,1] [,2] [,3] [,4]
[1,] 0 1 1 1
[2,] 0 0 1 1
[3,] 1 1 0 0
[4,] 1 0 0 0
This problem is a essentially a special case of enumerating all possible integral maximum flows. The added generality comes in handy when we make branching decisions and thereby need to look for solutions where specified matrix entries are all zero.
Let me define the flow network. For all k ∈ Z≥0, let [k] ≔ {1, 2, …, k}. Let there be m ∈ Z>0 rows and n ∈ Z>0 columns, let R : [m] → Z≥0 be the desired row sums, and let C : [n] → Z≥0 be the desired column sums. The flow network has a source vertex, s; for all i ∈ [m], a vertex ri ; for all j ∈ [n], a vertex cj ; and a sink vertex, t. There are arcs from s to each ri of capacity Ri, arcs from each ri to each cj of capacity 1, and arcs from each cj to t of capacity Cj.
Let’s assume that there is at least one solution, and hence that every maximum flow saturates all of the arcs leaving s and all of the arcs entering t. Given two maximum flows, their difference is a circulation. What this means is that, looking at the residual network, we can get from every maximum flow to every other maximum flow by repeatedly reversing the direction of a cycle.
I’ll demonstrate. The solution
1 1 1 0
1 1 0 0
0 0 1 1
0 0 0 1
corresponds to a residual flow network:
After reversing the cycle r1 → c4 → r4 → c3 → r1 to r1 → c3 → r4 → c4 → r1, the flow network
corresponds to a solution:
1 1 0 1
1 1 0 0
0 0 1 1
0 0 1 0
To get a backtracking solution, we repeatedly branch on whether a particular matrix entry is 0 or 1. Choose an entry, which corresponds to an arc in the residual network. Copy the network. In one recursive call, simply delete the arc. In the other, choose an arbitrary cycle that contains the arc and reverse it before deleting the arc. (If there is no such cycle, that entry is determined, so we can skip the call.)
- Arranging bars in ggplot
- How to smooth an arc
- ggplot of multiple geom_sf datasets gives mismatched legend colours
- I get an error when using {future} and {furrr} functions within a Golem Shiny App, what does it come from?
- ggpredict and quartiles: predictions with only one data point?
- How to properly create secondary y-axis with percentage scale and multiple lines in R?
- ipwtm function in R: First argument a vector
- How can I download GADM data in R?
- Use dplyr to compute "streaks" in column of data
- Count empty strings?
- How to show a ConditionalPanel when a row in a reactable table is selected?
- How to lookup and sum multiple columns in R
- Is there a way to make the bars' colors conditional to the column?
- How to assign values to a df$column from another df using conditions in R
- Is there a way to read Qlikview data object using R and perform an statistical operation and return results to Qlikview?
- R: Extracting characters from string vectors to data frame rows
- Else if statement to create a new column
- Calculate percentage in a data frame R
- How can I calculate sums of multiple columns without them being summed together into 1 column?
- How to convert a binary file with extension .GRD to .TXT in R?
- How to specify the size of a graph in ggplot2 independent of axis labels
- Using sqldf filter and group by in r dynamically
- Grouping data and reassembling rows as columns
- Coordinates of current mouse position on leaflet map with shiny
- read_csv drops 'f' from end of string
- wes_palettes: How to obtain color hex codes from a wesanderson palette when it set to continuous with more than the predefined colors
- ggplot2 change axis limits for each individual facet panel
- Mixing Rcpp modules and Rcpp::export
- How to create a forest plot that uses estimates obtained from ClubSandwich?
- how to include an abstract in a Rmd file