15
\$\begingroup\$

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\$.)

Task

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!

\$\endgroup\$
2
  • 4
    \$\begingroup\$ 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\$. \$\endgroup\$
    – Yousername
    Nov 22, 2022 at 0:48
  • \$\begingroup\$ @Yousername Nice, that's the formula I had in mind as well. \$\endgroup\$
    – Aiden Chow
    Nov 22, 2022 at 0:53

14 Answers 14

7
\$\begingroup\$

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)
\$\endgroup\$
7
\$\begingroup\$

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                 ~
\$\endgroup\$
4
\$\begingroup\$

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.

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

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
\$\endgroup\$
3
\$\begingroup\$

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.

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

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]\$.

\$\endgroup\$
2
\$\begingroup\$

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

enter image description here

\$\endgroup\$
2
\$\begingroup\$

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!

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

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.

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

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.

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
1
0
\$\begingroup\$

05AB1E, 8 bytes

LœDδδ@€`

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

Try it online or verify all test cases.

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)
\$\endgroup\$
0
\$\begingroup\$

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 = n;                //     start with y = n
      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 = n;              //       start with x = n
        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               //
}                           //
\$\endgroup\$
0
\$\begingroup\$

Charcoal, 37 bytes

≔…⁰Nθ⊞υ⟦⟧Fθ≔ΣEυE⁻θκ⁺κ⟦μ⟧υF⊕υEυEι⭆κ›μξ

Attempt This Online! Link is to verbose version of code. Explanation: Based on @Ausername's Vyxal answer.

≔…⁰Nθ

Start with a range from 0 to N.

⊞υ⟦⟧Fθ≔ΣEυE⁻θκ⁺κ⟦μ⟧υ

Generate all of the permutations of that range.

F⊕υEυEι⭆κ›μξ

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.