Random spanning tree of a rectangular grid

Question

Significantly harder version of Spanning tree of a rectangular grid.

Background

A spanning tree (Wikipedia) of an undirected graph is a subgraph that is a tree which includes all of the vertices of the original graph. The following is an example of a spanning tree of a 4-by-4 grid graph.

Task

Given two positive integers w and h, output a randomly generated spanning tree of the grid graph which has w vertices horizontally and h vertices vertically. Your program/function should be able to generate every possible spanning tree with nonzero probability.

One possible algorithm to solve this task is random minimum spanning tree, which calculates the minimum spanning tree of the given graph with randomized edge weights.

Input and output

The input is two positive integers w and h.

The output is a representation of a spanning tree. You can choose any representation that can describe such a graph without ambiguity, which includes (but is not limited to):

• ASCII-formatted grid
• A standard graph structure, e.g. adjacency matrix, adjacency list, incidence matrix...
• A list of pairs of numbered vertices

Please specify the output format in your submission.

Scoring & winning criterion

The standard code-golf rules apply. The shortest valid submission in bytes wins.

Example I/O

w=3, h=2

• ASCII grid

+-+-+
| |
+ +-+

• Adjacency matrix

0 1 0 1 0 0
1 0 1 0 1 0
0 1 0 0 0 0
1 0 0 0 0 0
0 1 0 0 0 1
0 0 0 0 1 0

• List-of-vertex-pairs representation

[(0, 1), (0, 3), (1, 2), (1, 4), (4, 5)]

or

[((0, 0), (0, 1)),
 ((0, 0), (1, 0)),
 ((0, 1), (0, 2)),
 ((0, 1), (1, 1)),
 ((1, 1), (1, 2))]

w=1, h=1

The graph is a single vertex with no edges, and its only spanning tree is the graph itself.

Answer 1

Python 2, 134 bytes

from random import*
w,h=input();w+=1
t={1}
while 1:z=choice([{a,b}for a in t for b in{a-1,a+1,a-w,a+w}-t if b%w>0<b<w*h]);print z;t|=z

Try it online!

A small improvement over xnor's answer by using row size w+1 instead of w and not using the zeroth column. For example, the following coordinates are used for the input 3,2:

1-2-3
| | |
5-6-7

Answer 2

Wolfram Language (Mathematica), 146 bytes

Block[{c,g=GridGraph@{##}},Graph[Range[1##],Join@@Reap[Do[c@n/._c:>#0[Sow[#<->n];n],{n,RandomSample@AdjacencyList[g,c@#=#]}]&@1][[2]],Options@g]]&

Try it online!

Based on my answer to the question Maze Generation.

Returns a Graph object.

For example, w = 20, h = 20 gives:

Answer 3

Ruby, 159 bytes

->w,h{c=(v=[*1..w].product [*1..h]).product;((f,(a,b)),(g,(d,e))=c.shuffle.map{|z|[z,z.sample]};(c=c-[f,g]+[f+g];p(a,b,d,e))if(a-d).abs+(b-e).abs<2)while c[1]}

Try it online!

Uses simple Kruskal's algorithm with a few pessimizations (no union-find, inefficient - and non-uniform! - sampling of the purely virtual edge list, returns via stdout), at a byte cost relatively close to Value Ink's Prim implementation.

Prints each edge as a set of four lines; if you want something slightly more sensible, replace p(a,b,d,e) with p [a,b,d,e] at the cost of one byte.

Unsqueezed version:

->w, h{
 v=[*1..w].product [*1..h]
 c=v.product
 while c.size > 1
  (f, (a, b)), (g, (d, e)) = c.shuffle.map{|z| [z, z.sample]}
  if (a-d).abs + (b-e).abs < 2
   c = c - [f, g] + [f + g]
   p [a,b,d,e]
  end
 end
}

Answer 4

Jelly, 28 bytes

,þ;Z$ṡ€2ẎẊḣ1;ẎḟL’ɗÐḟ@ḣ1ʋ¥ƬƊṪ

Try it online!

A dyadic link taking the width and height as its arguments and returning a list of pairs of vertices indicating the edges of the random minimum spanning tree. Based on Prim’s algorithm with the edge costs randomised.

Explanation

,þ                           | Outer table using pair function
    $                        | Following as a monad:
  ;                          | - Concatenate to:
   Z                         | - Transposed table
     ṡ€2                     | Split each into overlapping lists of length 2
        Ẏ                    | Join outer lists
         Ẋ                   | Randomise order
                          Ɗ  | Following as a monad:
          ḣ1                 | - First list item (still in a list)
                        ¥Ƭ   | - Repeat following as a dyad, collecting up results, until no new result seen (will have the randomised list of vertex pairs as its right argument)
            ;          ʋ     | - Concatenate to the following as a dyad:
             Ẏ               |   - Join outer lists (making list of vertices seen so far)
                 ɗÐḟ@        |   - Keep only items from the randomised list of edges where the following is false:
              ḟ              |     - Filter out the vertices already used
               L             |     - Length
                ’            |     - Decrement by 1
                     ḣ1      |   - First list item (still in a list)
                           Ṫ | Final iteration of the above

Answer 5

Python 2, 136 bytes

from random import*
w,h=input()
t={0}
while 1:z=choice([{a,b}for a in t for b in{a-~a%w/~w,a+a%w/~w,a-w,a+w}-t if-1<b<w*h]);print z;t|=z

Try it online!

Prints edges as two-element set of vertices given by single-number index, terminating with error. The strategy is to to build up the set of vertices t in the tree until it contains the whole rectangle rectangle. At each step, we add an edge to the spanning tree consisting of a vertex in t and one of its neighbors that's not in t, and we add the new vertex to t. We search for neighbors by adding one of {1,-1,w,-w} to the 1D index with some trickery to avoid unwanted wraparounds, and checking that the result lies within the bounds of the rectangle.

---

Python 2, 142 bytes

from random import*
w,h=input()
t={0}
while 1:z=choice([{a,b}for a in{k/w+k%w*1jfor k in range(w*h)}-t for b in t if(a-b)**4==1]);print z;t|=z

Try it online!

Prints edges as two-element sets of complex numbers, terminating with error.

Answer 6

Ruby, 185 164 bytes

A huge mess. Outputs a vertex-pair list, where vertex coordinates are complex numbers in the form x+yi.

Long story short, it takes all vertices that have already been chosen, randomly picks a neighbor that has not been picked before, and attaches it to the graph, then repeats the process until all vertices have been chosen.

• -4 bytes by optimizing r>=0&&i>=0 to r|i>=0 -- If either number is negative, the bit-or will ensure that the combined result is negative.
• -17 bytes by realizing my filter function in the second neighbor check could be switched to a simple set intersection...

->w,h,*e{*v=q=0i;d=1,-1,1i,-1i
(q=v.flat_map{|x|d.map{|c|x+c}.select{|e|r,i=e.rect;r|i>=0&&r<w&&i<h}-v}.sample
(v<<q;e<<[(d.map{|c|q+c}&v).sample,q])if q)while q;e}

Try it online!

Explanation

->w,h,*e{                                       # Proc taking 2 arguments, e=[]
         *v=q=0i;                               # Add first vertex 0+0i to list
                 d=1,-1,1i,-1i                  # Save 4 cardinal directions
(                                     )while q  # While there is a valid neighbor:
 q=                                             # Set next vertex to:
   v.flat_map{|x|d.map{|c|x+c}                  # Get all neighbors to used vertices
      .select{|e|                               # Filter neighbors by:
                 r,i=e.rect                     # Get real/imaginary components
                 r|i>=0&&r<w&&i<h               # Vertex coordinates are in-bounds
             }
      -v                                        # Filter already-used vertices
    }.sample                                    # Pick a random valid neighbor
 (                                   )if q      # If a neighbor was found:
  v<<q                                          # Add it to the vertex list
  e<<[                                          # Add an edge to the edge list.
      (                                         # First vertex of edge is:
       d.map{|c|q+c}                            # Get vertex neighbors
       &v                                       # Intersect w/ used vertices
      ).sample                                  # Pick one by random
      ,q]                                       # Second vertex of edge is neighbor
                                                # (end while)
e                                               # Return the edge list

Answer 7

K (ngn/k), 64 bytes

{e@&~~':i{@[x;&|/x=/:y;:;&/x y]}\e:0N?,/(2':'m),+'2':m:x#i:!*/x}

Try it online!

arg: w,h pair. result: list of vertex pairs.

i:!*/x create the list 0 .. (w*h)-1 and assign to i

m:x# reshape to a w-by-h matrix m

2': pairs of neighbouring rows

+' transpose each (make them rows of pairs)

( ), prepend

2':'m pairs of neighbouring cells in each row

,/ concat into a single list

e:0N? shuffle and assign to e for "edges"

i{ }\ scan the edges with the function in { } and a starting value i. the left arg will map vertices to their "tree ids" in the forest. initially the vertex ids and tree ids coincide.

@[x;&|/x=/:y;:;&/x y] amend the current forest by merging the tree(s) corresponding to the ends of the new edge

~': which forests match the previous ones? boolean list

e@&~ select from e where not

Answer 8

Charcoal, 77 63 bytes

ＮθＮηＪ⊗‽θ⊗‽ηＰ+  ¦+Ｗ‹№ＫＡ+×θη«Ｊ⊗‽θ⊗‽η¿¬℅ＫＫ«≔⌕ＡＫＶ ι¿ι«Ｐ+  Ｐ✳⁻χ⊗‽ι²+

Try it online! Link is to verbose version of code. Outputs a whitespace-bordered ASCII grid. Explanation:

ＮθＮη

Input the width and height.

Ｊ⊗‽θ⊗‽ηＰ+  ¦+

Jump to a random position and mark it with a + surrounded with spaces. (Unfortunately Charcoal's Multiprint operator special-cases a leading + so I have to output the + separately.)

Ｗ‹№ＫＡ+×θη«

Repeat until w*h +s have been output.

Ｊ⊗‽θ⊗‽η

Jump to a random position.

¿¬℅ＫＫ«

If the position is vacant,

≔⌕ＡＫＶ ι

find any neighbouring spaces,

¿ι«

and if there is at least one, then

Ｐ+  Ｐ✳⁻χ⊗‽ι²+

surround the current position with spaces, draw a - or | in a random matching direction, and finally draw a + in the current position.

Answer 9

JavaScript (ES6),  151 147 145  143 bytes

Takes input as (width)(height). Returns a list of pairs of numbered vertices.

w=>g=h=>(m=1,n=a=[],F=v=>[++v%w&&v,--v%w&&v-1,v+w,v-w].map(V=>V<0|V/w/h|m>>V&1|Math.random()<.5||F(V,m|=1<<V,n=a.push([v,V]))))``|~n+w*h?g(h):a

Try it online!

Commented

w =>                        // w = width
g = h => (                  // h = height
  m = 1,                    // m = bitmask of visited vertices
  n =                       // n = number of visited vertices - 1
  a = [],                   // a[] = pairs of connected vertices
  F = v =>                  // F is a recursive function, taking the current vertex v
    [ ++v % w && v,         //   try v + 1 if (v + 1) mod w is not equal to 0
                            //   we temporarily increment v to coerce it to a number
      --v % w && v - 1,     //   decrement v; try v - 1 if v mod w is not equal to 0
      v + w,                //   unconditionally try v + w
      v - w                 //   unconditionally try v - w 
    ].map(V =>              //   for each new vertex V:
      V < 0 |               //     abort if V is negative
      V / w / h |           //     abort if V is greater than or equal to w * h
      m >> V & 1 |          //     abort if V was already visited
      Math.random() < .5 || //     abort with 50% probability
      F(                    //     otherwise, do a recursive call:
        V,                  //       using the new vertex
        m |= 1 << V,        //       update the bitmask of visited vertices
        n = a.push([v, V])  //       append [v, V] to a[] and update n
      )                     //     end of recursive call
    )                       //   end of map()
)`` |                       // initial call to F with v = [''] (zero'ish)
~n + w * h ?                // if n is not equal to w * h - 1:
  g(h)                      //   try again
:                           // else:
  a                         //   success: return a[]

Answer 10

R, 156 bytes

function(w,h){b=rbind(x<-1:(s=w*h),c(x+1,1:(s-h)+h))[,1:w*-h][,sample(s+s-h-w)]
y=b[,1]
while(!all(z<-matrix(b%in%y,2)))y=rbind(y,b[,colSums(z)==1][1:2])
y}

Try it online!

A function taking the width and height and returning a two-matrix of 1-indexed pairs of points (numbered from top left, moving down and then right). The footer also prints an ASCII representation. Implements Prim’s algorithm.