# Inspiration

There is a problem on the most recent AMC 12B test, the one held on November 16, 2022, which goes like this:

(AMC 12B 2022, Question 17)
How many $$\4\times4\$$ arrays whose entries are $$\0\$$s and $$\1\$$s are there such that the row sums (the sum of the entries in each row) are $$\1\$$, $$\2\$$, $$\3\$$, and $$\4\$$, in some order, and the column sums (the sum of the entries in each column) are also $$\1\$$, $$\2\$$, $$\3\$$, and $$\4\$$, in some order? For example, the array $$\begin{bmatrix}1&1&1&0\\0&1&1&0\\1&1&1&1\\0&1&0&0\end{bmatrix}$$satisfies the condition.

(If any of you are curious the answer is $$\576\$$.)

Your task is, given some positive integer $$\N\$$, output all $$\N\times N\$$ binary matrices such that the row sums are $$\1,2,\ldots,N\$$ in some order, as well as the column sums.

# Test Cases

N ->
Output
-------
1 ->
1

2 ->
1 1
1 0

1 1
0 1

1 0
1 1

0 1
1 1

3 ->
1 0 0
1 1 0
1 1 1

1 0 0
1 0 1
1 1 1

0 1 0
1 1 0
1 1 1

0 1 0
0 1 1
1 1 1

0 0 1
1 0 1
1 1 1

0 0 1
0 1 1
1 1 1

1 0 0
1 1 1
1 1 0

1 0 0
1 1 1
1 0 1

0 1 0
1 1 1
1 1 0

0 1 0
1 1 1
0 1 1

0 0 1
1 1 1
1 0 1

0 0 1
1 1 1
0 1 1

1 1 0
1 0 0
1 1 1

1 1 0
0 1 0
1 1 1

1 0 1
1 0 0
1 1 1

1 0 1
0 0 1
1 1 1

0 1 1
0 1 0
1 1 1

0 1 1
0 0 1
1 1 1

1 1 0
1 1 1
1 0 0

1 1 0
1 1 1
0 1 0

1 0 1
1 1 1
1 0 0

1 0 1
1 1 1
0 0 1

0 1 1
1 1 1
0 1 0

0 1 1
1 1 1
0 0 1

1 1 1
1 0 0
1 1 0

1 1 1
1 0 0
1 0 1

1 1 1
0 1 0
1 1 0

1 1 1
0 1 0
0 1 1

1 1 1
0 0 1
1 0 1

1 1 1
0 0 1
0 1 1

1 1 1
1 1 0
1 0 0

1 1 1
1 1 0
0 1 0

1 1 1
1 0 1
1 0 0

1 1 1
1 0 1
0 0 1

1 1 1
0 1 1
0 1 0

1 1 1
0 1 1
0 0 1


# Note

The reason why I'm not doing a challenge on simply outputting the number of matrices that satisfy the condition is because there is a pretty simple formula to calculate that number. Brownie points if you can figure out that formula, and why it works!

This is , so shortest code in bytes wins!

• For any $N$, there is only one possible $N × N$ matrix in which the sum of the first row is 1, the sum of the second row is 2, the sum of the first column is $N$, the sum of the first column is $N-1$, etc. (In this matrix a right triangular shape should be formed). From here you can allow different orders of the rows by multiplying by $N!$ and then again for the columns to get the final formula $N!^2$. Nov 22, 2022 at 0:48
• @Yousername Nice, that's the formula I had in mind as well. Nov 22, 2022 at 0:53

# Jelly, 8 bytes

Œ!cþþẎṠ


A monadic Link that accepts a positive integer and yields a list of the binary matrices.

Try it online!

### How?

We can first arrange the set of $$\N\$$ sorted rows any way we like leading to $$\N!\$$ matrices with sorted rows. Each of these matrices will have column sums from $$\1\$$ through to $$\N\$$ in order, so all column-wise permutations will be distinct, so there are $$\N!^2\$$ such matrices.

We can create these matrices by noting that each number in the set $$\[1,N]\$$ is greater than or equal to exactly $$\N\$$ of the elements in the set (including itself).

Thus a table of $$\\geq\$$ between two permutations of the first $$\N\$$ natural numbers is such a table, e.g.:

$$\\geq\$$ 1 3 2
3 0 1 0
2 0 1 1
1 1 1 1

Where one permutation defines the column sums (directly - i.e. $$\\{1,3,2\}\$$, above) and the other defines the row sums (in reverse order - i.e. $$\\{3,2,1\}\$$, above, defines the sums $$\\{1,2,3\}\$$)

Œ!cþþẎṠ - Link: integer, N
Œ!       - all permutations (of [1..N])
   - use as both arguments of:
þ    -   table of:
þ     -     table of:
c      -       n-choose-k (a golf to get a positive integer when n>=k else 0)
Ẏ  - tighten to a list of the sub-tables
Ṡ - sign (convert the positives to ones)


# APL (Dyalog Classic), 34 33 bytes

{{~⍉¨⍵∘.⍀⍨↓∘.≠⍨⍳1+≢⊃⍵}⍣2⍣⍵⊂0 0⍴⍬}


Try it online!

Returns an array of boxed matrices. +1 for a flat structure by putting , somewhere in the first few characters.

Illustrates another way to get $$\f(N)=N!^2\$$:
For each $$\N\times N\$$ matrix that satisfies this property, we can invert 0s and 1s, then insert a row and column of 1s to get a $$\(N+1)\times(N+1)\$$ matrix that also has this property. Furthermore, each such resulting matrix is uniquely determined by predecessor, row, and column. Since there are $$\N+1\$$ positions in which a row or column can be inserted, $$\f(N+1)=(N+1)^2f(N)\$$, and $$\f(0)=1\$$ (one empty matrix) completes the induction.

base 0x0 matrix                                  ⊂0 0⍴⍬
⍵ times:                {                   }  ⍣⍵
1...N+1                             ⍳1+≢⊃⍵
N+1 row inserts           ⍵∘.⍀⍨↓∘.≠⍨
N+1 column inserts      ⍉¨                 ⍣2
invert                 ~


# J, 27 22 bytes

i.@!([A."1"{A.)>:/~@i.


Try it online!

-5 thanks to ovs!

Create the "step" matrix, get all row permutations, then to each of those apply all permutations again, but to each row at the same time -- this is equivalent to applying it to the columns.

• &.|: -> "1 for -2. And ([A."1"0 3 A.) would work as well, but doesn't save bytes
– ovs
Nov 22, 2022 at 11:46
• Thanks. That insight is worth even more because "1"{ does save bytes. Nov 22, 2022 at 14:52

# Vyxal, 11 bytes

ɾ:v≤Ṗv∩vṖÞf


Try it Online!

ɾ           # Push range(1, n+1)
v         # Over each...
ɾ: ≤        # Check if it's less than each of range(1, n+1)
Ṗ       # Get all permutations
v∩     # Transpose each
vṖ   # Get permutations of each
Þf # Flatten by one layer


# Python + NumPy, 94 bytes

from numpy import*
f=lambda n,p=0:1//n*[e:=eye(n)]or[1-w.T@e[j]for j in e<1for w in f(n+p,~p)]


Attempt This Online!

Same logic as before but implemented in matrix algebra avoiding he expensive insert.

### Python 3 + NumPy, 96 bytes (@att)

from numpy import*
f=lambda n,p=0:[insert(w,i,1+p,p)for i in r_[:n]for w in f(n+p,~p)]or[eye(0)]


Try it online!

### Python 3 + NumPy, 99 bytes

from numpy import*
f=lambda n,p=1:[insert(w,i,p,p)for i in r_[:n+1-p]for w in f(n-p,1-p)]or[eye(0)]


Try it online!

This works by alternating between inserting rows of zeros and columns of ones at every possible position.

• -3 bytes
– att
Nov 23, 2022 at 20:50
• @att Nice! I had a hunch something like this should be possible but couldn't find it. Nov 24, 2022 at 12:52

# PARI/GP, 62 bytes

n->forperm(n,p,forperm(n,q,print(matrix(n,n,x,y,p[x]>=q[y]))))


Attempt This Online!

Let $$\p\$$ and $$\q\$$ runs over all permutations of $$\1,\dots,n\$$. For each $$\p\$$ and $$\q\$$, construct an $$\n\times n\$$ binary matrix where the element at position $$\(x,y)\$$ ($$\1\$$-indexed) is $$\1\$$ if and only if $$\p[x]\ge q[y]\$$.

# Nibbles, 8.5 bytes (17 nibbles)

+.;p,$.@.$._$/  Port of Jonathan Allan's Jelly answer: upvote that. Sadly, Nibbles comes-out half-a-byte longer.  ,$            # 1..input
p              # get all permutations of that
;                 # and save this list of lists
.                  # now map over each list
.@          #   mapping over each saved list
.$._ # element-wise mapping over each x,y $    #       sign of
/   #       x integer-divided by y
+                   # finally, flatten by one level


# JavaScript (Node.js), 132 bytes

n=>P(n).flatMap(x=>P(n).map(y=>x.map(u=>y.map(v=>u+v<n))))
P=(n,i=n)=>n?i--?[...P(n,i),...P(--n).map(r=>r.splice(i,0,n)&&r)]:[]:[[]]


Try it online!

• @Arnauld It should be fixed now.
– tsh
Dec 1, 2022 at 2:05

# Python 3, 147 145 bytes

lambda n:[[[k[l]for l in j]for k in i]for j in p(range(n))for i in p([1]*i+[0]*(n-i)for i in range(1,n+1))]
from itertools import*;p=permutations


Try it online!

Based on my comment to this challenge. First generates a right triangular shaped matrix of 1s, then makes all possible different permutations of rows and columns. Outputs a list of 2D lists. -2 bytes thanks to Mukundan314.

# Python 3, 132 121 116 115 bytes

lambda n:[[[1-(l>k)for l in j]for k in i]for i,j in product(*[[*permutations(range(n))]]*2)]
from itertools import*


Try it online!

Uses the method entailed in Jonathan Allan's answer. -12 bytes thanks to Mukundan314, -5 bytes thanks to att.

• -5 second
– att
Nov 22, 2022 at 4:29
• -1 byte for second answer Nov 22, 2022 at 4:56
• -7 by (slightly ;-P ) rearranging the loop Try it online! Nov 23, 2022 at 2:11
• @loopywalt You can probably post that as a separate response since it seems fairly different in its method. Nov 23, 2022 at 2:46

# Ruby, 125 ... 79 bytes

->n{a=*[*1..n].permutation;a.product(a).map{|r,c|r.map{|x|c.map{|y|x>y ?0:1}}}}


Try it online!

Switched to Jonathan Allan's approach.

# Jelly, 11 bytes

>€ḶŒ!Z€Œ!€Ẏ


Try it online!

Port of my Vyxal.

 €          # Over each of...
# implicit range(1, n+1)
>           # Are they greater than...
Ḷ         # range(0, n)
Œ!       # Permutations
Z€     # Transpose each
Œ!€  # Permutations of each
Ẏ # Flatten by one level


# 05AB1E, 8 bytes

LœDδδ@€


Port of @JonathanAllan's Jelly answer, so make sure to upvote him as well!

Explanation:

L         # Push a list in the range [1, (implicit) input]
œ        # Get all permutations of this list
D       # Duplicate it
δ      # Apply double-vectorized:
δ     #  Apply double-vectorized:
@    #   a >= b check
€  # Then flatten the list of lists of matrices one level down
# (after which the result is output implicitly)


# JavaScript (ES6), 146 bytes

This is a naive solution based on bit masks and brute force.

Prints all valid matrices.

n=>{for(k=1<<n*n;k--;M+2>>n-~n&&console.log(m))for(M=m=[],y=n;y--;M|=1<<r|1<<c+n)for(m[y]=[c=r=0],x=n;x--;r+=q,c+=k>>x*n+y&1)m[y][x]=q=k>>y*n+x&1}


Try it online!

### Commented

n => {                      // n = input
for(                      // first loop:
k = 1 << n * n;         //   start with k = 2 ** (n * n)
k--;                    //   decrement until k = 0
M + 2 >> n - ~n         //   if bits 1 to n * 2 (0-indexed)
&&                      //   are all set in M:
console.log(m)        //     print the matrix
)                         //
for(                    //   second loop:
M =                   //     M = bit mask
m = [],               //     m[] = matrix
y--;                  //     decrement until y = 0
M |= 1 << r |         //     update the bit mask
1 << c + n       //     with row and column bits
)                       //
for(                  //     third loop:
m[y] = [c = r = 0], //       initialize m[y], c and r
x--;                //       decrement until x = 0
r += q,             //       increment r if q is set
c += k >> x * n + y //       increment c if the cell at
& 1            //       (y, x) is set
)                     //
m[y][x] =           //       set m[y][x] to
q =                 //       q, defined as
k >> y * n + x    //       the cell at (x, y)
& 1               //
}                           //


# Charcoal, 37 bytes

≔…⁰Ｎθ⊞υ⟦⟧Ｆθ≔ΣＥυＥ⁻θκ⁺κ⟦μ⟧υＦ⊕υＥυＥι⭆κ›μξ


≔…⁰Ｎθ


Start with a range from 0 to N.

⊞υ⟦⟧Ｆθ≔ΣＥυＥ⁻θκ⁺κ⟦μ⟧υ


Generate all of the permutations of that range.

Ｆ⊕υＥυＥι⭆κ›μξ
`

Generate the comparison matrices between each pair of incremented permutation and permutation.