# Generate a regular graph

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

• A random regular graph would be a nice challenge.
– user108721
Jan 11, 2022 at 16:57
• @graffe I considered that, but I'm not a big fan of "Generate a random X" challenges Jan 11, 2022 at 17:19
• 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. Jan 12, 2022 at 15:38

# 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 --^

• Here's a six that is the same idea ḶṙⱮU<. Jan 11, 2022 at 1:52
• @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. Jan 11, 2022 at 1:56
• Nice, forgot it would vectorise! Jan 11, 2022 at 2:12

# 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!

• As we are allowed a flat list for output: 46 ato.pxeger.com/… Jan 12, 2022 at 7:22

# Pari/GP, 33 bytes

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


Try it online!

# Jelly, 6 bytes

Ḷ_þ%Ɗ<


Try It Online!

# 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:

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.

# 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)

• Am I missing something, or is the assignment to y unnecessary? Aug 19, 2022 at 21:51
• @emanresuA Good catch! That was probably left from a previous version. Aug 20, 2022 at 15:21

# 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)


# 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

• Bogosort style approach, very interesting Jan 11, 2022 at 15:34

# R, 4940 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.

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

# Charcoal, 16 bytes

ＮθＮηＥθ⮌⭆θ‹﹪⁺ιλθη


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

Ｎθ                  First input n as a number
Ｎη                Second input k as a number
θ              First input
Ｅ               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


# 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.)

# Wolfram Language (Mathematica), 41 bytes

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


Try it online!

• 40 bytes
– att
Jan 11, 2022 at 19:06

# Ruby, 49 bytes

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


Try it online!

# 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.

# 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

# Vyxal, 7 bytes

ɾṘ≥:(…ǔ


Try it Online!

# Knight, 49 bytes

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


Try it online!

# 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!

# 05AB1E, 7 bytes

LR@Dv=Á


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

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


# brev, 82

(lambda(n k)((over(with i((over(if(or(= i it)(> i k))0 1))x)))(make'()n(iota n))))

• Ah no this has a bug, I just realized. Some rows will have one 1 too many. Aug 21, 2022 at 6:54