snippet FoxtrotUniform <p>Ever needed (or wanted) to generate a tree (in this case, a graph on n vertices with n-1 edges) at random? Dismayed that the obvious method (adding a 1-2 edge, then randomly picking a vertex to connect 3 to, then 4) doesn't produce all possible trees (1-3-2 simply can't be done)? Your prayers are answered! This code uses Pr&uuml;fer sequences (for which Google generates <i>no</i> useful introductory hits) to describe trees... turns out you can rank the n<sup>n-2</sup> labelled trees, generate the Pr&uuml;fer sequence corresponding to that rank, then reconstruct the tree from the sequence.</p> <p>This code is pretty much a straight implementation of the pseudocode in [http://www.math.mtu.edu/~kreher/cages.html|Combinatorial Algorithms: Generation, Enumeration, and Search].</p> <CODE> use strict; use POSIX qw(floor); use Data::Dumper; # rank_to_prufer(r, n) # Generates the Prufer sequence for the n-vertex tree of rank # r. sub rank_to_prufer { my (\$rank, \$n) = @_; my @prufer = (); for(my \$i = \$n - 2; \$i > 0; \$i--) { my \$new = \$rank % \$n + 1; unshift @prufer, \$new; \$rank = POSIX::floor((\$rank - \$new + 1) / \$n); } return @prufer; } # prufer_to_tree(seq) # Generates the tree corresponding to the Prufer sequence seq sub prufer_to_tree { my @prufer = @_; my \$n = scalar @prufer + 2; my @edges = (); my @degrees = (1) x \$n; push @prufer, 1; for (0 .. \$n - 3) { my \$i = \$prufer[\$_] - 1; \$degrees[\$i]++; } for (0 .. \$n - 2) { my \$x = \$n-1; while(\$degrees[\$x] != 1) {\$x--;} my \$y = \$prufer[\$_] - 1; \$degrees[\$x]--; \$degrees[\$y]--; my @edge = (\$x+1, \$y+1); push @edges, \@edge; } return @edges; } # example call -- generate a random 6-vertex tree my @tree = &prufer_to_tree(&rank_to_prufer(rand(1296), 6)); </CODE>