Efficiently enumerate the boolean matrix of sparsity k such that no rows and columns are all 0s.

Question

Is there a way to enumerate the boolean matrix of $k$ entries of $1$ with no rows and columns all being $0$s?

e.g.

$k=1$, $\begin{bmatrix}1\end{bmatrix}$

$k=2$, $\begin{bmatrix}1 & 1\end{bmatrix}$ $\begin{bmatrix}1 \\ 1\end{bmatrix}$ $\begin{bmatrix}1 & 0\\ 0 & 1\end{bmatrix}$ $\begin{bmatrix}0 & 1\\1 & 0\end{bmatrix}$

$k=3$, $\begin{bmatrix}1 & 1 & 1\end{bmatrix}$ $\begin{bmatrix}1 & 1 & 0\\ 0&0&1\end{bmatrix}$ $\begin{bmatrix}1 & 1\\0&1\end{bmatrix}$ $\begin{bmatrix}1 & 0&1\\0&1&0\end{bmatrix}$ $\begin{bmatrix}1 & 1\\1&0\end{bmatrix}$ $\begin{bmatrix}0&1 & 1\\1&0&0\end{bmatrix}$ $\begin{bmatrix}1&0&0\\0&1 & 1\end{bmatrix}$ $\begin{bmatrix}1&0\\1 & 1\end{bmatrix}$ $\begin{bmatrix}0&1&0\\1&0 & 1\end{bmatrix}$ $\begin{bmatrix}0&1\\1 & 1\end{bmatrix}$ $\begin{bmatrix}0&0&1\\1 & 1&0\end{bmatrix}$ $\begin{bmatrix}1 \\ 1\\1\end{bmatrix}$ $\begin{bmatrix}0&1 \\0& 1\\1&0\end{bmatrix}$ $\begin{bmatrix}0&1 \\ 1&0\\0&1\end{bmatrix}$ $\begin{bmatrix}1&0 \\ 0&1\\0&1\end{bmatrix}$ $\begin{bmatrix}0&1 \\ 1&0\\1&0\end{bmatrix}$ $\begin{bmatrix}1&0 \\ 0&1\\1&0\end{bmatrix}$ $\begin{bmatrix}1&0 \\ 1&0\\0&1\end{bmatrix}$ $\begin{bmatrix}1&0&0\\0&1&0\\0&0&1\end{bmatrix}$ $\begin{bmatrix}1&0&0\\0&0&1\\0&1&0\end{bmatrix}$ $\begin{bmatrix}0&1&0\\1&0&0\\0&0&1\end{bmatrix}$ $\begin{bmatrix}0&1&0\\0&0&1\\1&0&0\end{bmatrix}$ $\begin{bmatrix}0&0&1\\1&0&0\\0&1&0\end{bmatrix}$ $\begin{bmatrix}0&0&1\\0&1&0\\1&0&0\end{bmatrix}$

$k=4$,...

There is a trivial inductive approach that we can just consider where to put the $k$th $1$ based on all of the $(k-1)$th configurations. However, this will make $k!$ duplications for each unique configuration.

Another possible approach is that we can maybe partition $k$ by the rows and columns first. Say $k=4$, partition the rows into $2,1,1$ and cols into $1,1,2$ then enumerate the $3 \times 3$ configurations that satisfy the row col number of $1$s correspondingly. But we still need to consider how to enumerate the balanced matrix efficiently.

Now is there an easy way to enumerate all possibilities? If not, can we find an easy enumerator for just half of all the cases?

Answer 1

Here's one possible scheme.

We'll fill in the $1$s of the up-to-$n$-by-$n$ matrix one at a time, but going in lexicographic order. The first $1$ can be in any of the positions $(1,1), (1,2), \dots, (1,n)$. If we just placed a $1$ in position $(i,j)$, the next $1$ can be in any of the positions $$(i,j+1), (i,j+2), \dots, (i,n), (i+1,1), (i+1,2), \dots, (i+1,n).$$ This ensures that no zero rows are created, but it doesn't do anything about zero columns. So we must do something about that as well...

Let's keep track of which columns (up to the last column used) are empty so far, and how many of them there are. This has two effects:

• If there are $a$ more $1$s to enter after the current one, $b$ empty columns, and the rightmost $1$ already entered appears in column $c$, the current $1$ should be entered no further right than column $c+(a-b)+1$ (creating up to $b-a$ more empty columns).
• If $a$ ever equals $b$, we switch to a mode in which we can only place a $1$ to fill an existing empty column.

How efficient is this scheme? Each possible matrix we want will be listed exactly once. So the only overhead is the overhead of keeping track of the empty columns described above. We can definitely limit this to $O(n)$ processing per $1$ we place, and therefore $O(n^2)$ per matrix, but we could probably be more efficient as well...