Download the raw code.
use v6;
#returns a list of all forests with depth <= $dm $n nodes, trees which are
#before ($d,$nmax,$max)
#returns all forests of depth <= $n
multi forests(Int $n, 0, Int $nmax = $n, $max = Inf) {[],}
multi forests(Int $n, 1, Int $nmax = $n, $max = Inf) {[[] xx $n],}
multi forests(Int $n, Int $d, Int $nmax where {$n < $nmax}, $max = Inf) {forests($n,$d)}
multi forests(Int $n, Int $d, Int $nmax = $n, $max = Inf) {
return forests($n,$d-1) if $nmax < $d;
gather {
for trees($nmax,$d) Z 1..$max -> $tree, $index {
for forests($n-$nmax,$d,$nmax,$index) -> $forest {
take [$tree, @$forest];
}
}
take forests($n,$d,$nmax-1);
}
}
#returns all trees of depth $n
multi trees(1, 1) {[],}
multi trees(Int $n, 1) {()}
multi trees(Int $n, 2) {[[] xx ($n-1)],}
multi trees(Int $n, Int $d, Int $nmax, $max = Inf, $dmax = $d) {
($dmax > $d or $nmax > $n) and return trees($n,$d);
gather {
for trees($n,$d) Z 1..$max -> $tree,$i{
take $tree;
}
}
}
multi trees(Int $n, Int $d) {
gather {
for $d..$n -> $cn {
for trees($cn-1,$d-1) Z 1..* -> $tree,$index {
for forests($n-$cn,$d-1,$cn-1,$index) -> $forest {
take [$tree,@$forest];
}
}
}
}
}
sub even_trees(Int $n) {
my $maxd = $n div 2;
for 2..$maxd -> $cd {
for ceiling($n/2)..($n-$cd) -> $cn {
for trees($cn, $cd) Z 1..* -> $t1, $max {
for trees($n-$cn, $cd,$cn,$max,$cd) -> $t2 {
say represent([$t1,@$t2]);
}
}
}
}
}
sub odd_trees(Int $n) {
my $maxd = ($n-1) div 2;
for 1..$maxd -> $cd {
for $cd..($n-1-$cd) -> $cn {
for trees($cn, $cd) Z 1..* -> $t1, $max {
for $cd..($cn,($n-1-$cn)).min -> $dn {
for trees($dn, $cd,$cn,$max) Z 1..* -> $t2, $max2 {
for forests($n-$cn-$dn-1,$cd,$n-$cn-$dn-1,$max2) -> $w {
say represent([$t1,$t2,@$w]);
}
}
}
}
}
}
}
multi represent($tree) {
my $rep = represent($tree,1)[0];
$rep ~~ s/\-\d+$//;
return $rep;
}
multi represent($tree,Int $n) {
return $n,$n+1 if $tree.elems == 0;
my $c = $n+1;
my $rep = "$n";
for @$tree -> $subtree {
my ($r,$s) = represent($subtree,$c);
$c=$s;
$rep ~= "-$r-$n";
}
return $rep,$c;
}
multi MAIN(1) {say "1"}
multi MAIN(2) {say "1-2"}
multi MAIN(Int $n) {
even_trees($n);
odd_trees($n);
}
The program fails for N = 8:
$ nom solutions/t5/simon 8
1-2-3-2-4-2-5-2-1-6-1-7-1-8
1-2-3-2-4-2-5-2-6-2-1-7-1-8
1-2-3-2-4-2-5-2-6-2-7-2-1-8
1-2-3-4-3-2-5-2-1-6-7-6-1-8
1-2-3-4-3-5-3-2-1-6-7-6-1-8
1-2-3-4-3-5-3-2-1-6-7-6-8-6
1-2-3-4-3-2-5-6-5-2-1-7-8-7
1-2-3-4-3-2-5-2-6-2-1-7-8-7
1-2-3-4-3-5-3-2-6-2-1-7-8-7
1-2-3-4-3-5-3-6-3-2-1-7-8-7
1-2-3-4-5-4-3-2-1-6-7-8-7-6
1-2-1-3-1-4-1-5-1-6-1-7-1-8
1-2-3-2-1-4-5-4-1-6-7-6-8-6
1-2-3-2-1-4-5-4-1-6-7-6-1-8
1-2-3-2-1-4-5-4-1-6-1-7-1-8
1-2-3-2-4-2-1-5-6-5-1-7-8-7
1-2-3-2-4-2-1-5-6-5-1-7-1-8
1-2-3-2-4-2-1-5-6-5-7-5-1-8
1-2-3-2-4-2-5-2-1-6-7-6-1-8
1-2-3-2-4-2-5-2-1-6-7-6-8-6
1-2-3-2-4-2-5-2-6-2-1-7-8-7
1-2-3-4-3-2-1-5-6-7-6-5-1-8
1-2-3-4-3-2-5-2-1-6-7-8-7-6
1-2-3-4-3-5-3-2-1-6-7-8-7-6
Which corresponds to these trees:
8 3 8 3 4 3 4
| | | \ / \ /
7--1--2--4 1----2 8--1--2--5
| | | / \ / \
6 5 7 6 5 7 6
8 5 8 4
| | | |
7--6--1--2--3--4 7--6--1--2--3--5
8 4
| |
7--6--1--2--3--5 8--7--1--2--3--4
|
5--6
6 6 4
| | |
8--7--1--2--3--4 8--7--1--2--3--5
|
5
4
|
8--7--1--2--3--5 8--7--6--1--2--3--4--5
|
6
8 2 8 6--7
\ / |* |
7--1--3 7--6--1--2--3 8--1--2--3
/|\ | |
6 5 4 4--5 4--5
7 8 4 8 4
\ / |* | |
6--1--2--3 3--2--1--7--8 7--1--2--3
| | |
4--5 5--6 5--6
7 8 4 8 4
| | | | |
6--5--1--2--3 7--6--1--2--3
|
5
1 4 3
| | |
7--6--1--2--3 8--7--1--2--4
| / \
5 6 5
5--6--7 5
| |
8--1--2--3--4 8--7--6--1--2--3--4
4
|
8--7--6--1--2--3--5
The two trees marked with an asterisk are isomorphic and hence duplicates. Presumably this occurs because tree traversal order isn't normalized away quite right.
Not much to complain about here.
The even_trees and odd_trees routines are a bit deep, indentation-wise.
It's difficult to follow what's going on in there.
Efficiency doesn't really apply since the program is incorrect.
The program makes good, effective use of language features. Returning lists of values, passing around data using built-in data structures...
The two represent multis are really in an inner-outer relationship, and
should probably have been factored to reflect that. Could declare one inside
the other, for example.
This code doesn't waste much time getting its point across.