Some PERL code for detecting/displaying "toroidal" trees "invariant under a half-turn"
From: David Halitsky (dhalitsky_at_cumulativeinquiry.com)
Date: 07/31/04
- Next message: Larry Chen: "FORTRAN "Source Code to Flow Chart Converter" Available"
- Previous message: Krzysiek: "How to calculate volatility (variance od returns) from total derivative of asset"
- Messages sorted by: [ date ] [ thread ]
Date: 31 Jul 2004 09:22:19 -0700
**********************************************************
Relevant sci.math background thread for this posting is:
------------------------------------------
DAG/POSET "consultancy fee" conjecture:
sole thread here for all future postings
------------------------------------------
Background
In the above mentioned thread, Dr. Jerry Rieper presents/
proves an algorithm for defining/enumerating all
"orderable DAGS", i.e. all DAGs that can be
consistently ordered so that their structure can
be correctly represented by a dim 2 poset.
This algorithm will be reviewed by Dr. David Wagner
(U Waterloo Ca) upon his return from vacation, but
Jerry's algorithm is believed to be correct by
Robin Houston, Guenter Stertenbrink, and Stas Busygin
who also did considerable work on the problem.
If Dr. Wagner's review of Dr. Rieper's algorithm
confirms its correctness (or if Dr. Wagner can correct
this algorithm so that it accomplishes the purpose),
then the results of Dr. Robert Jamison (Clemson)
concerning:
"trees invariant under a half-turn"
can more than likely be extended to
"oDAGs (ordered DAGs)" invariant under a half-turn.
To see VISUALLY (not ALGEBRAICALLY) what Dr. Jamison means
by "tree inavariant under a half-turn", consider the
labelled bracketing:
[ a [ b [ c [ d e ] ] ] ]
A B C D C B A
and its structure-preserving representation as the
dim 2 poset:
y
^
|
8 a
7 b
6 c
5 d
4 e
3 D
2 C
1 B
0 A
0 1 2 3 4 5 6 7 8 -->x
where:
i) one extension of the poset is 012345678 and the other
is 081726354
ii) the "directed edge" relationship in this diagram is
((xi,yi),(xj,yj)) such that xi < xj, yi <yj and no
(xk,yk) with xi < xk < xj and yi < yk < yj (i.e.
no intervening ancestor(s) of (xj,yj) and descendant(s)
of (xi,yi).
Given this diagram, suppose one takes the square with edges
on x=0, x=8, y=0 y=8 and adds "tabs" to this square so that
one can roll it up into torus such that x=0 is one unit
distant from x=8 and y=0 is one unit distant from y=8.
Then clearly, we can re-slice this torus back into the plane
so that its vertices are disposed symmetrically about the
point C(4,4)
y
^
|
8 c
7 d
6 e
5 D
4 C
3 B
2 A
1 a
0 b
0 1 2 3 4 5 6 7 8 -->x
Such trees can be termed "invariant" under a half-turn
and Dr. Jamison has proved algebraically precisely which
trees can have this property; his proof will be posted
shortly to sci.math. (Note that the second diagram does
not display "the same" oDAG as the first, and Dr. Jamison's
proof therefore defines a new type of equivalence class
on oDAGs.)
But in the meantime, William F. (Bill) Mann has written
a neat program which accepts a permutation of 0,...,n
and detects whether this permutation will yield a tree
invariant under a half-turn. For the above case, the
output of this program "ht" (for "half-turn") is:
********************************************
Permutation 0,8,1,7,2,6,3,5,4 Length 9
2,1,3,0,4,8,5,7,6 4.0 2.0 0 7
0,4,1,3,2,7,6,8,5 8.5 6.5 4 2
. 8 . . . . . . . . 8 . . . . . . .
. . . 7 . . . . . . . . 7 . . . . .
/ - - - - 6 - - \ . . . . . 6 . . .
| . . . . . . 5 | . . . . . . . 5 .
| . . . . . . . 4 . . . . . . . . 4
| . . . . . 3 . | . . . . . . 3 . .
| . . . 2 - - - | - - - - 2 . . . .
| . 1 . | . . . | . . 1 . | . . . .
0 . . . | . . . | 0 . . . | . . . .
| 8 . . | . . . | . 8 . . | . . . .
\ - - 7 - - - - / . . . 7 | . . . .
. . . . | 6 . . . . . . . | 6 . . .
. . . . | . . 5 . . . . . | . . 5 .
. . . . | . . . 4 . . . . | . . . 4
. . . . | . 3 . . . . . . | . 3 . .
. . . . 2 - - - - - - - - 2 . . . .
. . 1 . . . . . . . . 1 . . . . . .
0 . . . . . . . . 0 . . . . . . . .
7,6,8,5,0,4,1,3,2 4.0 6.5 0 2
4,8,5,7,6,2,1,3,0 8.5 2.0 4 7
. 8 . . . . . . . . 8 . . . . . . .
. . . 7 . . . . . . . . 7 . . . . .
. . . . / 6 - - - - - - - \ 6 . . .
. . . . | . . 5 . . . . . | . . 5 .
. . . . | . . . 4 . . . . | . . . 4
. . . . | . 3 . . . . . . | . 3 . .
/ - - - 2 - - - \ . . . . 2 . . . .
| . 1 . | . . . | . . 1 . | . . . .
0 . . . | . . . | 0 . . . | . . . .
| 8 . . | . . . | . 8 . . | . . . .
| . . 7 \ - - - | - - - 7 / . . . .
| . . . . 6 . . | . . . . . 6 . . .
| . . . . . . 5 | . . . . . . . 5 .
| . . . . . . . 4 . . . . . . . . 4
| . . . . . 3 . | . . . . . . 3 . .
\ - - - 2 - - - / . . . . 2 . . . .
. . 1 . . . . . . . . 1 . . . . . .
0 . . . . . . . . 0 . . . . . . . .
*********************************************
And this output is obtained simply by running
the PERL code given below with the input command
line:
--------------------
ht 0,8,1,7,2,6,3,5,4
--------------------
(with or without directing your output, e.g.
-----------------------------
ht 0,8,1,7,2,6,3,5,4 > ht.out
-----------------------------
Algebraically AND algorithmically nimble
folks will readily see the gist of Dr. Jamison's
proog in Bill's code:
**************************************************************************
Bill's PERL code for program "ht"
#!/usr/bin/perl -w
# Find and display the halfturn symmetries of a comma-separated permutation.
# For length N permutations, all complete mod N symmetries are detected.
# Note: the perl % operator is equivalent to mod only for positive intergers.
# Copyright 1996,1997,1999,2003 Cumulative Inquiry Inc.
# Brownsboro, AL USA
# All Rights Reserved
# $RCSfile: halfturn,v $ $Revision: 1.3 $ $Date: 2003/03/04 18:09:16 $
# halfturn [-d] 1,2,0,...
# -d means not to display the torus
{
@ARGV and $arg_d = $ARGV[0] eq '-d' and shift @ARGV;
@ARGV == 1 or die "Usage: halfturn [-d] 1,2,0,...\n";
@P = split(/,/, $ARGV[0]);
$N = @P; # size of the permutation
$L = $N - 1; # index of the last element
@D = (@P, @P); # permutation doubled
$C = $N / 2; # center of tile
# check tree for validity
for $d (@P) {
$d =~ /^\d+$/ or die "$d is not a number\n";
$T[$d]++;
}
for ($d = 0; $d < @T; $d++) {
defined $T[$d] or warn(" $d is missing\n"), $err = 1, next;
$T[$d] == 1 or warn(" $d is duplicated\n"), $err = 1, next;
}
$err and exit;
print "Permutation ", join(',', @P), " Length ", $N, "\n";
$mt = 1; # empty flag
xpos: # locate a center of symmetry
for ($xpos = $L; $xpos >= 0; $xpos--) {
$ypos = ($D[0] + $D[$xpos]) % $N;
for ($i = 1; $i < $L; $i++) {
($D[$i] + $D[$N + $xpos - $i]) % $N == $ypos or next xpos;
}
$mt = 0; # found a center of symmetry
$x1 = $xpos / 2;
$x2 = ($xpos + $N) / 2;
$y1 = $ypos / 2;
$y2 = ($ypos + $N) / 2;
@p1 = &perm($x1, $y1); # generate the four related permutations
@p2 = &perm($x2, $y2);
@p3 = &perm($x1, $y2);
@p4 = &perm($x2, $y1);
if ($p{&shape(@p1)}++ == 0) { # eliminate duplicate shapes
$p{&shape(@p2)}++ ? &display(\@p1) : &display(\@p1, \@p2);
} elsif ($p{&shape(@p2)}++ == 0) {
&display(\@p2);
}
if ($p{&shape(@p3)}++ == 0) {
$p{&shape(@p4)}++ ? &display(\@p3) : &display(\@p3, \@p4);
} elsif ($p{&shape(@p4)}++ == 0) {
&display(\@p4);
}
}
$mt and &display();
}
# return the permutation shifted to be centered at (x,y), the centers,
# and the selected tile coordinates
sub perm {
my($x,$y) = @_;
my @S;
my $l = int($N + $x - $C + .5) % $N;
my $b = int($N + $y - $C + .5) % $N;
for ($i = 0; $i < $N; $i++) {
$S[$i] = ($N + $D[$l + $i] - $b) % $N;
}
(join(',', @S), $x, $y, $l, $b);
}
# return the shifted permution and its centering
sub shape {
my($p,$xc,$yc) = @_;
join('/', $p, 2*$xc & 1, 2*$yc & 1);
}
# display the specified halfturn permutations
sub display {
my(@L,@R,@B,@T);
for $a (@_) {
printf("%s %4.1f %4.1f %2d %2d\n", @$a);
}
$arg_d and return; # omit the display
for ($y = 2*$N-1; $y >= 0; $y--) {
print ' ';
for ($x = 0; $x <= 2*$N-1; $x++) {
$c = $y % $N;
$c += $c < 10 ? ord('0') : ord('a') - 10;
(2*$N + $D[$x] - $y) % $N == 0 and print(' ', chr $c), next;
$c = '.';
for $a (@_) {
my(undef,$xc,$yc,$l,$b) = @$a;
my $r = $l + $N - (2*$xc+$N & 1);
my $t = $b + $N - (2*$yc+$N & 1);
$x == $l && $y == $b and $c = '\\', last;
$x == $r && $y == $t and $c = '\\', last;
$x == $l && $y == $t and $c = '/', last;
$x == $r && $y == $b and $c = '/', last;
($x == $l || $x == $r) && $y > $b && $y < $t and $c = '|', last;
($y == $b || $y == $t) && $x > $l && $x < $r and $c = '-', last;
}
print ' ', $c;
}
print "\n";
}
}
- Next message: Larry Chen: "FORTRAN "Source Code to Flow Chart Converter" Available"
- Previous message: Krzysiek: "How to calculate volatility (variance od returns) from total derivative of asset"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
