Graph-Maker-Other
view release on metacpan or search on metacpan
t/Catalans.t view on Meta::CPAN
foreach my $N (0 .. 7) {
my $rightarm = Graph::Maker->new('Catalans', N => $N,
rel_type => 'rotate_rightarm');
my $leftarm = Graph::Maker->new('Catalans', N => $N,
rel_type => 'rotate_leftarm',
rel_direction => 'down');
foreach my $edge ($leftarm->edges) {
my @mirrored = map{balanced_str_transpose($_)} @$edge;
ok (!!$rightarm->has_edge(@mirrored), 1);
}
# foreach my $edge ($rightarm->edges) {
# my @mirrored = map{balanced_str_transpose($_)} @$edge;
# ok (!!$leftarm->has_edge(@mirrored), 1);
# }
}
#------------------------------------------------------------------------------
# rotate_rightarm
# rotate_rightarm_num_edges() returns the number of edges in rotate_rightarm
# graph.
# A002057 (different offset)
# Recurrence R(n) = sum(k=1,n-1, (R(k)+C(k))*R(n-k-1)) where C(n)=Catalan number.
#
sub rotate_rightarm_num_edges {
my ($n) = @_;
return binomial(2*$n-1, $n-2) * 4/($n+2);
}
{
# directed
my @A127632_samples # OFFSET=0, intervals
= (1, 1, 3, 11, 44, 185, 804, 3579, 16229, 74690, 347984, 1638169);
foreach my $N (0 .. 7) {
my $graph = Graph::Maker->new('Catalans', N => $N,
rel_type => 'rotate_rightarm',
countedged => 1);
ok (scalar($graph->vertices), $Catalan_number[$N]);
# 0,0,1,4,14,48,165,572
ok (scalar($graph->edges), rotate_rightarm_num_edges($N),
"rotate_rightarm num edges N=$N");
my @predecessorless_vertices = $graph->predecessorless_vertices;
ok (scalar(@predecessorless_vertices), 1,
'rotate_rightarm predecessorless_vertices count');
ok ($predecessorless_vertices[0], '10'x$N,
'rotate_rightarm predecessorless_vertices is 10101010');
my @successorless_vertices = $graph->successorless_vertices;
ok (scalar(@successorless_vertices),
$N==0 ? 1 : $Catalan_number[$N-1],
'rotate_rightarm successorless_vertices count');
# A127632 c(x*c(x)), where c(x) = Catalans gf
# 11, 44, 185, 804, 3579
# ENHANCE-ME: Some binomial formula ?
ok (num_intervals($graph), $A127632_samples[$N],
"rotate_rightarm num_intervals N=$N");
#
# David Callan, "A Combinatorial Interpretation of the Catalan Transform
# of the Catalan Numbers", http://arxiv.org/abs/1111.0996
}
}
{
# undirected
foreach my $N (0 .. 7) {
my $graph = Graph::Maker->new('Catalans', N => $N,
rel_type => 'rotate_rightarm',
undirected => 1,
countedged => 1);
ok (scalar($graph->vertices), $Catalan_number[$N]);
# FIXME: Graph.pm 0.9716 seems to have some dodginess in is_cyclic,
# provoking warning messages (but getting the right answer).
# ok (!!$graph->is_cyclic, $N>=4);
}
}
#---------------------------------
# rotate_rightarm
#
# Sebastian A. Csar, Rik Sengupta, Warut Suksompong, "On a Subposet of the
# Tamari Lattice", Information Processing Letters, volume 87, number 4,
# August 2003, pages 173-177
# https://arxiv.org/abs/1108.5690
# https://hal.archives-ouvertes.fr/hal-01283111
# http://dx.doi.org/10.1007/s11083-013-9305-5
{
# Figure 2 tree.
# * (1 ( ((23)4) ((56)7)))
# / \ reduced 1 ((23)4) (56)7
# 1 *
# / \ reduced by deleting parens enclosing last
# * *
# / \ / \
# * 4 * 7
# / \ / \
# 2 3 5 6
my @array = (1,0, 1,1,1,0,0,0, 1,1,0,0);
{
my @ret = Graph::Maker::Catalans::_vertex_name_type_bracketing(\@array);
ok(join('',@ret), '(1(((23)4)((56)7)))');
ok(join(',',@ret), '(1(((2,3)4)((5,6)7)))');
}
{
my @ret = Graph::Maker::Catalans::_vertex_name_type_bracketing_reduced(\@array);
ok(join('',@ret), '1((23)4)(56)7');
ok(join(',',@ret), '1((2,3)4)(5,6)7');
}
}
{
# Figure 3, C5
t/Catalans.t view on Meta::CPAN
foreach my $LRB ('L','R','B') {
my $href = $seen{$order}->{$LRB};
ok (scalar(keys %$href),
$want{$order}->{$LRB},
"N=$N count distinct $order $LRB");
}
}
}
#------------------------------------------------------------------------------
# filling
# A. Sapounakis, I. Tasoulas, P. Tsikouras, "On the Dominance Partial
# Ordering of Dyck Paths", Journal of Integer Sequences, volume 9, 2006,
# article 06.2.5.
# https://cs.uwaterloo.ca/journals/JIS/VOL9/Tsikouras/tsikouras67.html
#
# Dominance sequence = run length of 1s before each 0 in pre-order balanced
# binary.
# Filling = turn up every valley, so 01 -> 10 everywhere.
# 1100110100
# 1101011000
# ^^ ^^
{
# Section 2 run1s example.
my @array = (1,1,0,0,1,0,1,1,0,1,0,0);
ok (scalar(@array), 12);
my @run1s = Graph::Maker::Catalans::_vertex_name_type_run1s(\@array);
ok (scalar(@run1s), 6);
ok (join(',',@run1s), '2,0,1,2,1,0');
}
{
# Section 4 example filling.
my @array = (1,1,0,0,1,1,0,1,0,0);
my @fillings = Graph::Maker::Catalans::_rel_type_filling(\@array);
ok (scalar(@fillings), 1);
my @filling = @{$fillings[0]};
ok (join('',@filling), '1101011000');
}
# balanced string is "indecomposable" if its only return to zero is at its end,
# so "1 balanced 0"
sub balanced_str_is_indecomposable {
my ($str) = @_;
my $d = 0;
my $zeros = 0;
my @bits = split //, $str;
foreach my $i (0 .. $#bits) {
$d += ($bits[$i] ? 1 : -1);
if ($d==0 && $i < $#bits) { return 0; }
}
return 1;
}
ok ( balanced_str_is_indecomposable(''), 1);
ok ( balanced_str_is_indecomposable('10'), 1);
ok ( balanced_str_is_indecomposable('1100'), 1);
ok (! balanced_str_is_indecomposable('1010'), 1);
# Sapounakis, Tasoulas, Tsikouras, proposition 4.3 formula for num which are
# fillings, for $n >= 2.
# A086581 num Dyck words without 0011.
sub filling_num_predecessorful {
my ($n) = @_;
my $ret = 0;
foreach my $k (int($n/2) .. $n) {
$ret += (-1)**($n-$k) * binomial($k,$n-$k) * binomial(3*$k-$n, $k-1) / $k;
}
return $ret;
}
# foreach my $n (2 .. 10) { print filling_num_predecessorful($n),','; }
# print "\n";
{
# directed
# Sapounakis, Tasoulas, Tsikouras, proposition 4.2 balanced str is a
# filling (has a predecessor) if and only if str is indecomposable and
# does not contain 0011.
foreach my $N (2 .. 7) {
my $graph = Graph::Maker->new('Catalans', N => $N,
rel_type => 'filling',
countedged => 1);
ok (scalar($graph->edges), $Catalan_number[$N] - 1);
ok (scalar($graph->predecessorful_vertices),
filling_num_predecessorful($N));
my $end = ('1'x$N) . ('0'x$N);
my @successorless_vertices = $graph->successorless_vertices;
ok (scalar(@successorless_vertices), 1);
ok ($successorless_vertices[0], $end);
foreach my $v ($graph->vertices) {
# print "$v predecessors ",join(' ',$graph->predecessors($v)),"\n";
ok (scalar($graph->predecessors($v)) ? 1 : 0,
balanced_str_is_indecomposable($v) && $v !~ /0011/ ? 1 : 0,
'Sapounakis et al balanced binary is a filling');
# WRONG, not graded by num initial 1s.
# 012 3
# 111 0 0 0
# my $initial_1s = index($v,'0');
# if ($initial_1s < 0) { $initial_1s = 0; } # for $v empty string ""
# ok ($graph->path_length($v,$end), $N-$initial_1s);
}
}
}
{
# filling Ldepths successor is +1 at everywhere can increase
foreach my $N (0 .. 7) {
my $graph = Graph::Maker->new('Catalans', N => $N,
rel_type => 'filling',
vertex_name_type => 'Ldepths');
foreach my $from ($graph->vertices) {
my @successors = $graph->successors($from);
my @from = split /,/, $from;
my @to = @from;
my $any = 0;
foreach my $i (1 .. $#from) {
( run in 0.913 second using v1.01-cache-2.11-cpan-39bf76dae61 )