# -*- mode: cperl6; -*- # 2011 Perl 6 Coding Contest # Edgar Gonzàlez i Pellicer use v6; use LinkedLists; use Multiset; use Partition; # Tree class Tree { # Children has @.children; # Walk along a tree method walk() { # Recurse my Int \$pos = 1; # Gather my @result = gather { self.walk-rec(\$pos); } # Remove the last one, unless there is only one @result.pop unless @result == 1; # Return return @result; } # Walk along a tree # Recursive version method walk-rec(Int \$start is rw) { # Our number is... my Int \$ours = \$start++; take \$ours; # Any children? for @.children -> \$child { # Call for each children \$child.walk-rec(\$start); # Back to where we were take \$ours; } } } # Rooted trees my @rooted-trees; @rooted-trees[0] = []; @rooted-trees[1] = [ Tree.new ]; # Combine subtrees sub combine-subtrees(Array \$parts, Int \$i, Array \$cur, Array \$result) { # End? if \$i == \$parts.elems { # Add it \$result.push(Tree.new(children => \$cur.list)); } else { # How many of which cardinality my \$cardinality = \$parts[\$i].key; my \$how-many = \$parts[\$i].value; # Find all subtree multisets my @msets = multisets(rooted-trees(\$cardinality), \$how-many); # For each one for @msets -> \$mset { # Add it my \$len = \$mset.elems; \$cur.push(|\$mset); # Recurse combine-subtrees(\$parts, \$i + 1, \$cur, \$result); # Remove it \$cur.pop for ^\$len; } } } # Join two subtrees sub join-two-subtrees(Array \$trees, Array \$result) { # Loop for \$trees.keys -> \$i { for \$i ..^ \$trees.elems -> \$j { # Join one to the other (i.e., add one as children) my @children = \$trees[\$i].children; @children.push(\$trees[\$j]); \$result.push(Tree.new(children => @children)); } } } # Rooted trees sub rooted-trees(Int \$n) { # Generate them for @rooted-trees.elems .. \$n -> \$i { # Trees i my \$trees-i = []; # Find the partitions of \$n - 1 for int-partitions(\$i - 1) -> \$part { # Combine subtrees combine-subtrees(\$part.uniq-c, 0, [], \$trees-i); } # Set it @rooted-trees[\$i] = \$trees-i; } # Return them return @rooted-trees[\$n].list; } # We use Jordan's Theorem, as in: # # Roberto ARINGHIERI, Pierre HANSEN, Federico MALUCELLI # Chemical Trees Enumeration Algorithms # 4OR: A Quarterly Journal of Operations Research, 1(1), 67--83, 2003 # # but lifting the maximum degree restriction # Unrooted-trees sub unrooted-trees(Int \$n) { # Cases given \$n { # Negative or zero when * .. 0 { # Nothing return; } # One when 1 { # A single tree return Tree.new; } # Otherwise default { # Result my @result; # Parity? if \$n %% 2 { # Even # Partitions my @partitions = int-partitions(\$n - 1); my \$start = partitions-below-or-eq(@partitions, \$n div 2 - 1); # For each case for @partitions[\$start ..^ @partitions.elems] -> \$part { # Skip one- and two-element partitions next if \$part.elems <= 2; # Combine subtrees combine-subtrees(\$part.uniq-c, 0, [], @result); } # Join two subtrees join-two-subtrees(rooted-trees(\$n div 2), @result); } else { # Odd # Partitions my @partitions = int-partitions(\$n - 1); my \$start = partitions-below-or-eq(@partitions, \$n div 2); # For each case for @partitions[\$start ..^ @partitions.elems] -> \$part { # Skip one-element partitions next if \$part.elems == 1; # Combine subtrees combine-subtrees(\$part.uniq-c, 0, [], @result); } } # Return them return @result; } } } # Main sub MAIN(Str \$n-str) { # Number my Int \$n = \$n-str.Int; # Find the trees for unrooted-trees(\$n) -> \$tree { say(\$tree.walk.join('-')); } } # Call main # @maybe This should be done automatically? MAIN(|@*ARGS);