18
\$\begingroup\$

Inspired by this Mathematica.SE post

Given two positive integers \$n, k\$ with \$n > k \ge 1\$, output a binary \$n\times n\$ matrix such that every row and column contains exactly \$k\$ 1s, and the leading diagonal is all zero. This is the adjacency matrix of a regular graph.

You may output any valid matrix, and it does not have to be deterministic. You may output in any reasonable format, including a flat \$n^2\$ list, or a nested list, etc.

This is , so the shortest code in bytes wins.

Test cases

n, k -> output
2, 1 -> [[0, 1], [1, 0]]
5, 3 -> [[0, 1, 1, 1, 0], [1, 0, 0, 1, 1], [1, 1, 0, 0, 1], [1, 0, 1, 0, 1], [0, 1, 1, 1, 0]]
3, 1 -> [[0, 1, 0], [0, 0, 1], [1, 0, 0]]
5, 1 -> [[0, 1, 0, 0, 0], [1, 0, 0, 0, 0], [0, 0, 0, 1, 0], [0, 0, 0, 0, 1], [0, 0, 1, 0, 0]]
6, 2 -> [[0, 0, 0, 0, 1, 1], [1, 0, 0, 0, 1, 0], [1, 1, 0, 0, 0, 0], [0, 0, 1, 0, 0, 1], [0, 0, 1, 1, 0, 0], [0, 1, 0, 1, 0, 0]]
7, 6 -> [[0, 1, 1, 1, 1, 1, 1], [1, 0, 1, 1, 1, 1, 1], [1, 1, 0, 1, 1, 1, 1], [1, 1, 1, 0, 1, 1, 1], [1, 1, 1, 1, 0, 1, 1], [1, 1, 1, 1, 1, 0, 1], [1, 1, 1, 1, 1, 1, 0]]
\$\endgroup\$
3
  • 1
    \$\begingroup\$ A random regular graph would be a nice challenge. \$\endgroup\$
    – user108721
    Jan 11, 2022 at 16:57
  • \$\begingroup\$ @graffe I considered that, but I'm not a big fan of "Generate a random X" challenges \$\endgroup\$ Jan 11, 2022 at 17:19
  • 2
    \$\begingroup\$ I guess more specifically this is the adjacency matrix of a regular directed graph. Otherwise it would have to be symmetric, and there would be no solution for inputs like n=5, k=3. \$\endgroup\$ Jan 12, 2022 at 15:38

20 Answers 20

6
\$\begingroup\$

Jelly, 5 bytes

Ḷṙ`U<

Try It Online!

-1 byte thanks to Jonathan Allan

Ḷṙ`U<    Main Link; take n, k
Ḷ        [0, 1, 2, ..., n - 1]
  `      Apply with ^ on the left and right:
 ṙ       Rotate left; [[0, 1, 2, ..., n - 1], [1, 2, 3, ..., n - 1, 0], [2, 3, 4, ..., n - 1, 0, 1], ...]
   U     Reverse each; [[n - 1, n - 2, ..., 1, 0], [0, n - 1, n - 2, ..., 2, 1], [1, 0, n - 1, ..., 3, 2], ...]
    <    Is this less than k? [[0, ..., 1, 1, 1], [1, 0, ..., 1, 1], ...]
                                       ^-- k --^
\$\endgroup\$
3
  • 2
    \$\begingroup\$ Here's a six that is the same idea ḶṙⱮ`U<. \$\endgroup\$ Jan 11, 2022 at 1:52
  • 1
    \$\begingroup\$ @JonathanAllan oh, that's... a lot clever than all of the alternate ideas I came up with. Also, rotate can take a list on the right fine without needing the each in this case. \$\endgroup\$
    – hyper-neutrino
    Jan 11, 2022 at 1:56
  • 2
    \$\begingroup\$ Nice, forgot it would vectorise! \$\endgroup\$ Jan 11, 2022 at 2:12
5
\$\begingroup\$

Python 2, 45 bytes

Saved 15 bytes thanks to loopy walt! (Using the flat list output option.)

lambda n,k:[(i/n+~i)%n<k for i in range(n*n)]

An unnamed function accepting n and k that returns a list of booleans

Try it online!

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

Pari/GP, 33 bytes

f(n,k)=matrix(n,,i,j,(i-j-1)%n<k)

Try it online!

\$\endgroup\$
4
\$\begingroup\$

Jelly, 6 bytes

Ḷ_þ%Ɗ<

Try It Online!

\$\endgroup\$
4
\$\begingroup\$

Factor + math.matrices, 64 60 bytes

[ dupd dupd '[ - 1 - _ rem _ < 1 0 ? ] <matrix-by-indices> ]

The <matrix-by-indices> word postdates build 1525 (the one TIO uses), so here's a screenshot of running this in Factor's REPL:

enter image description here

This is a port of @alephalpha's Pari/GP answer. <matrix-by-indices> is a combinator with stack effect ( ... m n quot: ( ... i j -- ... elt ) -- ... matrix ). In other words, it lets you generate an mxn matrix but leaves the indices of each element (i, j) on top of the stack while you do so.

\$\endgroup\$
4
\$\begingroup\$

JavaScript (ES6), 50 bytes

Fixed version now using Jonathan Allan's formula
Thanks to @emanresuA for spotting some dead code (-2 bytes)

Expects (n)(k), returns a flat array of Boolean values.

n=>k=>[...Array(n*n)].map((_,x)=>(x+~(x/n)+n)%n<k)

Try it online! (raw output)
Try it online! (with post-processing)

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Am I missing something, or is the assignment to y unnecessary? \$\endgroup\$
    – emanresu A
    Aug 19, 2022 at 21:51
  • \$\begingroup\$ @emanresuA Good catch! That was probably left from a previous version. \$\endgroup\$
    – Arnauld
    Aug 20, 2022 at 15:21
3
\$\begingroup\$

MathGolf, 9 bytes

rxm<k(Å_╪

Outputs all rows concatenated to the stack.

Try it online.

Explanation:

r          # Push a list in the range [0, first (implicit) input n)
 x         # Reverse it to range (n,0]
  m        # Map over each integer:
   <       #  Check if it's larger than the second (implicit) input k
    k      # Push the first input n again
     (     # Decrease it by 1
      Å    # Loop that many times,
           # using the following 2 characters as inner code-block:
       _   #  Duplicate the top list
        ╪  #  Rotate the items in the list once towards the right
           # (after which the entire stack is output implicitly as result)
\$\endgroup\$
3
\$\begingroup\$

Apl

67 bytes

{{(⍴⍵)⍴{⍵[?⍨≢⍵]}∊⍵}⍣{((∧/2=/+/,+⌿)⍺)∧∧/~1 1⍉⍺}⍵ ⍵⍴⍺(⍺-⍵)/1 0}

incredebly ineffecent ,might be needlessly long

explantion

{{(⍴⍵)⍴{⍵[?⍨≢⍵]}∊⍵} shuffles array randomly untill

{∧/~1 1⍉⍺}digonal is all 0s

{((∧/2=/+/,+⌿)⍺)} and sum of all the rows and column is the same

{⍵ ⍵⍴⍺(⍺-⍵)/1 0} makes a n×n matrix of right argument with required 0s and 1s

\$\endgroup\$
1
  • \$\begingroup\$ Bogosort style approach, very interesting \$\endgroup\$ Jan 11, 2022 at 15:34
3
\$\begingroup\$

R, 49 40 38 bytes

Edit: -9 bytes thanks to Giuseppe

function(n,k)outer(1:n-1,1:n,`-`)%%n<k

Try it online!

Returns a matrix with values TRUE/FALSE (which evaluate to 1/0 in R). Add +3 bytes to output as a matrix with 1s and 0s directly.


Or my very lazy first attempt:

R, 93 bytes

function(n,k,`?`=rowSums){while(any(c(?(m=matrix(sample(1:0,n^2,T),n)),?t(m))-k,diag(m)))0;m}

Try it online!

Extremely inefficient (and often times-out on TIO even for the n≥5 test-cases), but will eventually (= nonzero probability) deliver the right answer each time.

Samples random matrices of 0, 1 until a solution is found that satisfies the rowSums, colSums & diag conditions.

\$\endgroup\$
2
  • \$\begingroup\$ 43 bytes golfing your sapply variant to use outer instead. \$\endgroup\$
    – Giuseppe
    Jan 11, 2022 at 12:53
  • \$\begingroup\$ @Giuseppe - Thanks a lot. That also beats all my current attempts using n x n+1 matrices, which I will now trash... \$\endgroup\$ Jan 11, 2022 at 14:12
2
\$\begingroup\$

Charcoal, 16 bytes

NθNηEθ⮌⭆θ‹﹪⁺ιλθη

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

Nθ                  First input `n` as a number
  Nη                Second input `k` as a number
     θ              First input
    E               Map over implicit range
        θ           First input
       ⭆            Map over implicit range and join
            ι       Row index
           ⁺        Plus
             λ      Column index
          ﹪         Modulo
              θ     First input
         ‹          Is less than
               η    Second input
      ⮌             Reversed
                    Implicitly print
\$\endgroup\$
2
\$\begingroup\$

Retina 0.8.2, 38 bytes

\d+
$*0
(0+) \1
$.1$*
.
$'$`$&¶
O$^`.+

Try it online! Link includes test cases. Output includes trailing newlines. Explanation:

\d+
$*0

Convert both inputs to strings of 0s.

(0+) \1
$.1$*

Subtract k from n and convert it to a string of 1s, so there are now n-k 0s and k 1s.

.
$'$`$&¶

Generate the cyclic permutations of that string in reverse order.

O$^`.+

Reverse the permutations into the desired order. (Normally the $ needs another line to specify the sort key but this is an edge case where it's not needed.)

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

Wolfram Language (Mathematica), 41 bytes

IdentityMatrix@#~RotateLeft~n~Sum~{n,#2}&

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 40 bytes \$\endgroup\$
    – att
    Jan 11, 2022 at 19:06
2
\$\begingroup\$

Ruby, 49 bytes

->a,b{a.times.map{|c|([0]*(a-b)+[1]*b).rotate c}}

Try it online!

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

APL (Dyalog Unicode), 16 bytes

{↑(-⍳⍵)⌽¨⊂⍵↑⍺⍴1}

Try it online!

Generates a fixed pattern by rotating each row by its index.


APL (Dyalog Unicode), 41 bytes

{{⍵[?⍨≢⍵]}⍤1⍣{(~1 1⍉⍺)∧.=≢∪+⌿⍺}↑⍵/⊂⍵↑⍺/1}

Try it online!

Shuffles each row until the conditions are satisfied.

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

APL+WIN, 23 21 bytes

Prompts for k followed by n. Index origin = 0

(⌽⍳n)⌽(n,n)⍴(n←⎕)↑⎕⍴1

Try it online!Thanks to Dyalog Classic

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

Vyxal, 7 bytes

ɾṘ≥:(…ǔ

Try it Online!

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

Knight, 49 bytes

;=xE P;=yE P;=i~1W>^x 2=i+1iO+0>y%+x%--/i x iTx x

Try it online!

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

Python3, 223 bytes:

from itertools import*
def f(n,k,c=[]):
 if len(c)==n:yield c
 else:
  for i in product(*[{0,not c or(i!=len(c)and sum([*zip(*c)][i])<k)}for i in range(n)]):
   if sum(i)==k:yield from f(n,k,c+[i])
g=lambda n,k:next(f(n,k))

Try it online!

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

05AB1E, 7 bytes

LR@Dv=Á

Pretty similar approach as my MathGolf answer.
Outputs all rows-lists on a separated line.

Try it online or verify all test cases.

Explanation:

L        # Push a list in the range [1, first (implicit) input n]
 R       # Reverse it to [n,1]
  @      # Check for each value if the second (implicit) input k >= the value
   D     # Duplicate this list
    v    # Pop and loop its size amount of times:
     =   #  Print the list with trailing newline (without popping)
      Á  #  Rotate its items once towards the right
\$\endgroup\$
1
\$\begingroup\$

brev, 82

(lambda(n k)((over(with i((over(if(or(= i it)(> i k))0 1))x)))(make'()n(iota n))))
\$\endgroup\$
1
  • \$\begingroup\$ Ah no this has a bug, I just realized. Some rows will have one 1 too many. \$\endgroup\$
    – Sandra
    Aug 21, 2022 at 6:54

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.