17
\$\begingroup\$

The unique-disjointness matrix ( UDISJ(n) ) is a matrix on all pairs of subsets of {1...,n} with entries $$ U_{(A,B)}=\begin{cases} 0, ~ if ~ |A\cap B|=1\\ 1, ~ otherwise \end{cases} $$

Or a bit less mathematical, it is the 2n times 2n matrix with a 0 in all entries where both indices have exactly one common 1 bit in their binary representation and a 1 in all other entries.

Example:

      0   1  10  11  100 101 110 111
     _______________________________
0   | 1   1   1   1   1   1   1   1
1   | 1   0   1   0   1   0   1   0
10  | 1   1   0   0   1   1   0   0
11  | 1   0   0   1   1   0   0   1
100 | 1   1   1   1   0   0   0   0
101 | 1   0   1   0   0   1   0   1
110 | 1   1   0   0   0   0   1   1
111 | 1   0   0   1   0   1   1   1

Write a program or function that takes an integer n as input and outputs the corresponding \$2^n \times 2^n\$ matrix.

Rules:

  • The values in the matrix can either be 0 / 1 (as numbers) or truthy/falsey
  • You are not allowed to permute the rows/columns of the matrix
  • This is the shortest solution (per language) wins
  • Your solution only needs to handle n between 2 and 10 (inclusive)

First 4 elements:

n=1:
1 1
1  

n=2:

1 1 1 1
1   1  
1 1    
1     1

n=3:

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   1     
1 1         1 1
1     1   1 1 1

n=4:
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 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     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 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 
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 1 
1     1   1 1 1   1 1 1 1 1 1 1 
\$\endgroup\$
0

22 Answers 22

7
\$\begingroup\$

Python, 72 bytes

lambda m:(q:=range(2**m))and(((i&j).bit_count()!=1for i in q)for j in q)

Attempt This Online!

\$\endgroup\$
7
\$\begingroup\$

05AB1E, 10 bytes

o<ÝDδ&b1ö≠

Outputs as a matrix with 1s and 0s.

Port of @mousetail's Python answer, so make sure to upvote that answer as well!

Try it online or verify the first 5 test cases.

Explanation:

o           # Push 2 to the power the (implicit) input-list
 <Ý         # Pop and push a list in the range [0,2**input)
   Dδ&      # Create a bitwise-AND table of it:
   D        #  Duplicate the list
    δ       #  Pop both lists and apply double-vectorized:
     &      #   Bitwise-AND
      b     # Then convert each inner value to a binary-string
       1ö   # Vectorized-sum its digits by converting from base-1 to a base-10 integer
         ≠  # Check for each that it's NOT equal to 1 (0 if 1; 1 otherwise)
            # (after which the matrix is output implicitly)
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Not again... Porting now lol \$\endgroup\$
    – The Thonnu
    Commented Jul 26, 2023 at 14:38
  • 1
    \$\begingroup\$ @TheThonnu Haha, déjà vu. ;) \$\endgroup\$ Commented Jul 26, 2023 at 14:39
7
\$\begingroup\$

Jelly, 8 bytes

2ṗ«'`§’n

Try it online!

            (input: n)
2ṗ          nth Cartesian power of [1, 2]: for example,
              [[1,1,1,1], [1,1,1,2], [1,1,2,1], ..., [2,2,2,2]] if n=4
  «'`       self-table by vectorized minimum
     §      sum each vector
      ’     subtract 1
       n    not equal to… (implicit argument: n)

Instead of 0b0011 & 0b0110 = 0b0010 we do 1,1,2,2 « 1,2,2,1 = 1,1,2,1.

Instead of checking popcount ≠ 1, we check sum ≠ n+1. §’n is shorter than ’§n1.

\$\endgroup\$
6
\$\begingroup\$

Vyxal, 66 bitsv2, 8.25 bytes

Eʁ:v⋏bvṠċ

Try it Online!

-4.75 bytes thanks to TheThonnu

The footer formats the resulting matrix into a nice grid like the test cases. Remove it for just a list of lists. Outputs inverted numbers (0s for 1s and 1s for 0s).

I somehow managed to generate like 3 other fractals while solving this, including an upside down triangle thing with the bottom off-center.

Explained

EDẊ‹sƛƒ⋏bT₃;ẇ­⁡​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁣‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁤‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁢⁡‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁢⁢‏⁠‎⁡⁠⁣⁤‏⁠⁠‎⁡⁠⁤⁣‏‏​⁡⁠⁡‌⁢⁢​‎‎⁡⁠⁢⁣‏⁠‎⁡⁠⁢⁤‏⁠⁠‏​⁡⁠⁡‌⁢⁣​‎‎⁡⁠⁣⁡‏⁠‎⁡⁠⁣⁢‏⁠‎⁡⁠⁣⁣‏⁠‏​⁡⁠⁡‌⁢⁤​‎‎⁡⁠⁤⁡‏⁠‎⁡⁠⁤⁢‏⁠‏​⁡⁠⁡‌­
ED             # ‎⁡Push three copies of n ** 2
  Ẋ            # ‎⁢Cartesian product of the range [1, n ** 2] and [1, n ** 2]
   ‹           # ‎⁣with all sublists decremented
    s          # ‎⁤and sorted
     ƛ     ;   # ‎⁢⁡To each pair
      ƒ⋏       # ‎⁢⁢  reduce by bitwise and
        bT₃    # ‎⁢⁣  is the length of truthy indices 1?
            ẇ  # ‎⁢⁤wrap into 2 ** n chunks
💎

Created with the help of Luminespire.

\$\endgroup\$
1
  • \$\begingroup\$ 9 bytes (or 8.25 with Vyncode) \$\endgroup\$
    – The Thonnu
    Commented Jul 26, 2023 at 14:59
4
\$\begingroup\$

Thunno 2, 10 bytes

2RẉDȷỌ€ʂ⁻Q

Try it online!

Outputs a nested list. The footer formats it into the grid. Port of Lynn's Jelly answer.

Explanation

2RẉDȷỌ€ʂ⁻Q  # Implicit input
2Rẉ         # [1,2] to the cartesian power of the input
   DȷỌ      # Outer product over minimum with itself
      €ʂ    # Sum each inner list
        ⁻Q  # Decrement, not equal to the input?
            # Implicit output

Old:

OLDȷÆ&ıḃ1ȷcḅ  # Implicit input
OL            # Push [0..2**n)
  DȷÆ&        # Outer product over bitwise AND
      ıḃ1ȷc   # Popcount of each
           ḅ  # Equals one?
              # Implicit output
\$\endgroup\$
4
\$\begingroup\$

Python, 66 bytes

lambda m:(q:=range(2**m))and[[(n:=i&j)>n^n-1for i in q]for j in q]

Attempt This Online!

mousetail's answer, but with bit operations instead of bit_count. We want to check that i&j (which we call n) doesn't have exactly one set bit, which means that it's a not power of two. We do this by checking that n>n^n-1, which is processed as n>n^(n-1). Let's check that this works in every case:

  • If n is a power of two, then n-1 has disjoint bits set to n and so their XOR is greater than n.
  • If n is any other positive value, then n and n-1 share the same leading bit, and the XOR cancels this bit making the result smaller than n.
  • For n==0, the result is 0, the same as n.

Annoyingly Python doesn't let us do the walrus assignment q:=range(2**m) in the iterable of a list comprehension, so the code has it assigned beforehand. loopy walt points out a better way to handle the two levels of iteration is using the classic divmod two-loop trick together with the classic zip/iter chunker.

61 bytes

lambda m:zip(*2**m*[((n:=j&j>>m)>n^n-1for j in range(4**m))])

Attempt This Online!

\$\endgroup\$
1
  • \$\begingroup\$ -3 just using the good ol' grouper. \$\endgroup\$
    – loopy walt
    Commented Jul 29, 2023 at 19:09
3
\$\begingroup\$

Arturo, 57 54 50 bytes

$->n[map^2n'x->map^2n=>[0<>^and dec<=<=and&-1x-1]]

Try it!

$->n[                     ; a function taking an argument n
    map^2n'x->            ; map over [1..2^n]; assign current elt to x
        map^2n=>[         ; map over [1..2^n]; assign current elt to &
            0<>           ; is zero not equal to
            and&-1x-1     ; bitwise and of current elts minus one
            <=<=          ; duplicated twice
            dec           ; minus one
            and           ; bitwise and
            ^             ; NOS to the TOS power
        ]                 ; end map
]                         ; end function
\$\endgroup\$
3
\$\begingroup\$

R, 55 53 bytes

function(n)(y=outer(x<-1:2^n-1,x,bitwAnd))^0-y%in%2^x

Try it online!

Rather than counting the number of on bits (which is very lengthy in R), tests the equivalent characterization of "equal to a power of 2"; then has to do some reshaping of the vector output of %in% to get back to the right shape matrix.

\$\endgroup\$
2
  • \$\begingroup\$ I cannot find anything on meta - is it generally allowed to output a matrix as a flat vector? \$\endgroup\$
    – pajonk
    Commented Jul 26, 2023 at 18:14
  • 1
    \$\begingroup\$ @pajonk hmm probably not. I didn't notice b/c of the footer, so I'll have to update it. \$\endgroup\$
    – Giuseppe
    Commented Jul 26, 2023 at 18:33
2
\$\begingroup\$

Nim, 119 bytes

import bitops
proc f(n:int)=
 let r=0..<1 shl n;for i in r:
  var s="";for j in r:s&= $int 1!=popcount i and j
  echo s

Attempt This Online!

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

Jelly, 10 bytes

2*Ḷ&þ`B§n1

Try it online!

How it works

2*Ḷ&þ`B§n1 - Main link. Takes n on the left
2*         - 2 ** n
  Ḷ        - [0, 1, ..., 2**n)
    þ`     - To every pair (a, b) in this range:
   &       -   Bitwise and
      B    - Convert all to binary
       §   - Sums
        n1 - Does not equal 1?
\$\endgroup\$
2
\$\begingroup\$

Pyth, 15 14 bytes

mmn1s&VdkQ=^U2

Try it online!

Explanation

mmn1s&VdkQ=^U2Q    # implicitly add Q
                   # implicitly assign Q = eval(input())
          =^U2Q    # Q = repeated cartesian product of [0,1] Q times
m             Q    # map lambda d over range(Q)
 m       Q         #   map lambda k over range(Q)
     &Vdk          #     d & k, vectorized
    s              #     sum bits
  n1               #     != 1
\$\endgroup\$
2
\$\begingroup\$

BQN (CBQN), 45 bytes 22 ‘bytes’

{1≠+´¨∧⌜˜⥊∾⌜⍟(𝕩-1)˜↕2}

I think the following is slightly more elegant, and it's the same number of characters but, alas, more bytes.

{1≠+´∘∧⌜˜⥊(↕2)∾⌜⍟𝕩⋈⟨⟩}

We operate only on bit-strings, rather than integers. ⥊⌜⍟(𝕩-1)˜↕2 gives us the list of binary strings of length 𝕩, which is then anded into a table, and summed: +´∘∧⌜˜. We then take only the 1≠ entries.

Attempt This Online!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Though I don't know the specifics of why, every BQN answer I've seen here counts 1 glyph as 1 byte. I think you can call these 22 bytes. \$\endgroup\$
    – chunes
    Commented Jul 26, 2023 at 22:37
  • \$\begingroup\$ @chunes Thanks, that makes quite a difference! \$\endgroup\$ Commented Jul 27, 2023 at 7:03
2
\$\begingroup\$

Ruby, 72 56 54 bytes

->n{(w=0...1<<n).map{|i|w.map{|j|a=i&j;(a&a-1)**a>0}}}

Try it online!

This employs one of my favourite bit-twiddling hacks. a&a-1 gives 0 if a has only one bit set. Unfortunately it also gives 0 if a==0 so we use the fact that any number (including 0) raised to the power 0 is 1 to catch this special case: (a&a-1)**a.

So now we have distinction between nonzero and zero numbers. The rules require two distinct values, so we use >0 to convert to true/false and we are done.

The footer in the linked TIO formats the output 2d array line by line, and converts the true/false to 1/0.

\$\endgroup\$
3
  • \$\begingroup\$ 52 bytes with Ruby 2.7 Numbered Parameters (TIO is stuck on 2.5.5) - ->n{(w=0...1<<n).map{|i|w.map{a=i&_1;(a&a-1)**a>0}}} \$\endgroup\$
    – Value Ink
    Commented Jul 27, 2023 at 20:10
  • \$\begingroup\$ @ValueInk oh wow thanks, that's new! You really have to check your versions. I still miss when you could write .5 instead of 0.5 \$\endgroup\$ Commented Jul 27, 2023 at 21:20
  • \$\begingroup\$ CG One Handed pointed it out to me earlier this week and it feels like a whole new world. Also, you can still save a byte on 2.5 by using j&=i;(j&j-1)**j>0 for 53 bytes Try it online! \$\endgroup\$
    – Value Ink
    Commented Jul 27, 2023 at 22:40
1
\$\begingroup\$

Factor + math.matrices math.unicode, 57 bytes

[ 2^ dup [ bitand bit-count 1 ≠ ] <matrix-by-indices> ]

Attempt This Online!

2^                           ! two to the input power
dup                          ! duplicate
[ ... ] <matrix-by-indices>  ! create an MxN matrix with indices on top of stack
bitand                       ! bitwise and
bit-count                    ! number of on bits
1 ≠                          ! not equal to one
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 15 bytes

oDL<ãε`&b1¢Θ}sô

Try it online!

Outputs a nested list. The footer formats it into the grid. Port of lyxal's Vyxal answer.

-1 thanks to @KevinCruijssen

Explanation

oDL<ãε`&b1¢Θ}sô  # Implicit input
oD               # Push 2 ** n and duplicate
  L<ã            # Cartesian product of [0..2**n) with itself
     ε      }    # Map over this list:
      `&         #  Bitwise AND of the pair
        b1¢Θ     #  Is the popcount equal to 1?
             sô  # Split into 2 ** n chunks
                 # Implicit output
\$\endgroup\$
1
  • \$\begingroup\$ can be ã (and golfing it some more would result in my 10 bytes answer, which I was already writing before I saw this answer tbh). \$\endgroup\$ Commented Jul 26, 2023 at 14:38
1
\$\begingroup\$

Nibbles, 11 bytes

.;`,^2$.@!=1+``@`&@$

Attempt This Online!

Returns a matrix with truthy values (positive numbers) for 1 and falsy values (0) for 0.

\$\endgroup\$
1
\$\begingroup\$

Raku, 52 bytes

{(^$_ X+&^$_).rotor($_)».&{!$_||$_!=1+<.msb}}o 1+<*

Try it online!

The version of Raku on TIO fails to parse the !$_||$_!=1+<.msb bit, presumably due to a bug, so I've expressed it there as !($_&&$_==1+<.msb), which is equivalent by De Morgan's law, but two bytes longer.

This is an anonymous function consisting of two separate anonymous functions composed together with o. The right-hand function is 1 +< *, which shifts the number 1 leftwards a number of bits given by its argument; that is, two to the power of the argument. That number is passed to the left-hand function, where the variable $_ gets its value.

  • ^$_ is a range of numbers from 0 up to one less than $_. For example, when the number passed to the first function is 3, this is the range 0..7.
  • X+& gives the cross product of one copy of that range with another using the bitwise-and operator +&.
  • .rotor($_) takes that flat crossed list and makes it into a square matrix.
  • ».&{ ... } recursively applies the code between the braces to each element of that matrix.
  • !$_ || $_ != 1 +< .msb tests whether each number is zero (!$_) or consists of only a single binary digit by comparing the number to 1 bit-shifted left a number of places equal to the number's most significant bit (1 +< .msb).
\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6), 74 bytes

n=>[...Array(1<<n)].map((_,y,a)=>a.map((_,x)=>(g=k=>k?k%2^g(k/2):1)(x&y)))

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 18 bytes

≔X²NθEθ⭆θ¬⁼¹Σ↨&ιλ²

Try it online! Link is to verbose version of code. Explanation:

  ²                 Literal integer `2`
 X                  Raised to power
   N                Input as a number
≔   θ               Save in variable
      θ             Saved variable
     E              Map over implicit range
        θ           Saved variable
       ⭆            Map over implicit range and join
               ι    Outer value
              &     Bitwise And
                λ   Inner value
             ↨   ²  Convert to base `2`
            Σ       Take the sum
         ¬⁼         Does not equal
           ¹        Literal integer `1`
                    Implicitly print
\$\endgroup\$
1
\$\begingroup\$

PARI/GP, 51 bytes

n->matrix(2^n,,i,j,sumdigits(bitand(i-1,j-1),2)!=1)

Attempt This Online!

\$\endgroup\$
1
\$\begingroup\$

Wolfram Language(Mathematica), 68 bytes

Golfed version. Try it online!

f@n_:=Array[Boole[1!=Tr@IntegerDigits[BitAnd[#-1,#2-1],2]]&,2^{n,n}]

Ungolfed version. Try it onlinne!

f@n_:=Table[If[Total[IntegerDigits[BitAnd[i-1,j-1],2]]!=1,1,0],{i,1,2^n},{j,1,2^n}]
\$\endgroup\$
1
\$\begingroup\$

JavaScript (Node.js), 65 bytes

n=>[...Array(1<<n)].map((_,y,a)=>a.map((_,x)=>(x&=y)&&+!(x&x-1)))

Try it online!

na

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