seeing a base-prime binary tree
I know this requires python2 or higher as well as bash3 or higher. Not sure about the other requirements, but my system has python-2.6.6, sage-4.6.1, graphviz-2.26.3, and bash-4.1.7(2)-release.
Here's baseprime-bintree as converted with the standard
sed "s/&/&/g;s//\>/g" for a livejournal non-autoformat post.
#!/bin/bash
if [ $# -lt 1 -o $1 -lt 3 ]; then
echo "usage: $0 nrows [args to pass to dot/neato...]"
echo "where nrows >= 3"
echo "typical dot args: -Tpng -o binarytree.png"
exit 1
else
rows=$1
shift
fi
treedata=$(sage -c 'execfile("BCLIB-sage");'\
'print("Result",[[[[0,0],[],1]]]+'\
'map(lambda k:map(lambda x:[[k,x],'\
'bpnorm(bptree([k,x])),bp2num(bpnorm(bptree([k,x])))],'\
'range(2^(k-1))),range(1,'"$rows"')))' |
fgrep "'Result'"|cut -d, -f2-|cut -d')' -f1)
expanded=$(echo "a=$treedata
"'print [["coord%s rep%s val:%d stop" % (p,q,r) for p,q,r in x] for x in a]'|
python)
halfparsed=$(
sed "s/'coord/\\n&/g;s/stop'/&\\n/g;s/[:[]/ &/g" <<< "$expanded"|
sed -n "s/, /,/g;/stop'/p")
nodes=$(
awk '{
gsub(/,/,".",$2);
gsub(/[][]/,"",$2);
print " " $2 " [label=\"" $4 $6 "\"];"}' <<<"$halfparsed")
gv1=$(echo -e 'digraph tree {\n node [shape=box];\n 0.0 -> 1.0;')
gv2=$(
r=2
while [ $r -lt $rows ]; do
cols=$(dc -e "2 $[ $r - 1 ] ^ p")
c=0
x=0
while [ $c -lt $cols ]; do
echo " $[ $r - 1].$(dc -e "0 k $c 2 / p") -> $r.$c"\
";"
#change previous line to the following to try attach-points for digraph
#"$(if [ $x -eq 0 ]; then echo ':ne'; else echo ':nw' ; fi);"
#in truth, it is harder to read, because the arrows curve and overlap---
#something I plan to fix
c=$[ $c + 1 ]
x=$[ 1 - $x ]
done
r=$[ $r + 1 ]
done
)
(echo "$gv1";echo "$gv2";echo "$nodes";echo "}")|dot "$@"
# see these for potential output tuning with graphviz 2.28:
# http://stackoverflow.com/questions/10902745/
# enforcing-horizontal-node-ordering-in-a-dot-tree
# https://mailman.research.att.com/pipermail/
# graphviz-interest/2010q2/007101.html
# the Ganser tree.gv script can be modified to work with graphviz 2.26.3
# by removing the second BEG_G section and changing TV_postfwd to TV_fwd
# in the first BEG_G section, but the output is not wide enough to
# prevent the nodes from overlapping (when I get a chance, I'll fix it)
# for now, the tree output is still pretty good, because it's a balanced
# and complete tree from the second row down
# this is how you might call the Ganser tree.gv script (if stored as
# ganser-tree.gv):
#(echo "$gv1";echo "$gv2";echo "$nodes";echo "}")|dot|
# gvpr -c -fganser-tree.gv|neato -n "$@"
And here's BCLIB-sage converted the same way:
# load with execfile(path)
def basep(n):
a=[]
if n>=2:
f=factor(n)
r=prime_range(1,f[len(f)-1][0]+1)
o=0
for i in range(len(r)):
#### print(i,r[i],o,f[o][0],f[o][1])
if f[o][0]==r[i]:
a.append(f[o][1])
o=o+1
else:
a.append(0)
return a
def bp2num(a):
if(len(a)):
p=[2]
while len(p)=len(a) else b[r]*a[x-r],range(w))
z=map(lambda a,b:a+b,z,y)
return bpnorm(z)
def bpconj(a):
if(len(a)):
if(a[0]):
c=[0,a[0]-1]+a[1:]
else:
c=[a[1]+1]+a[2:]
else:
c=[]
return c
def bptree(z):
r=z[0]
c=z[1]
p=[1,0]
o = map(lambda x:0,range(r))
for k in range(r):
print("@",k,":")
m = floor(c / 2);
m = m * 2
m = c - m
if m > 0:
print("R");
o[r - k - 1] = 0
c = floor((c - 1) / 2)
else:
print("L");
o[r - k - 1] = 1
c = floor(c / 2)
print(",c:=",c)
print(p)
for j in range(2, r + 1):
p.append(0);
print(o)
for k in range(len(o)):
print("op",k,o[k])
if o[k] > 0:
p[1] = p[1] + 1
else:
print("n",p[0])
print(p)
for j in range(p[0], 0, -1):
print("j",j,p[j])
p[j + 1] = p[j]
p[1] = 0
p[0] = p[0] + 1
print(p)
return p[1:]
def inbptree(p):
g = 1
o = []
while g>0:
if len(p)==1 and p[0]==0:
p=[]
if len(p)>0:
if p[0] > 0:
p[0] = p[0] - 1
o.append(1)
else:
for k in range(len(p)-1):
p[k] = p[k + 1]
p = p[0:len(p)-1]
o.append(0)
else:
g=0
r=0
c=0
for k in range(len(o)-1,-1,-1):
if o[k]>0:
r=r+1
c=c*2
else:
r=r+1
c=c*2+1
return (r,c)
Here's the output from ./baseprime-bintree 6 -Tpng -obinarytree.png
(view full size)
Here's baseprime-bintree as converted with the standard
sed "s/&/&/g;s//\>/g" for a livejournal non-autoformat post.
#!/bin/bash
if [ $# -lt 1 -o $1 -lt 3 ]; then
echo "usage: $0 nrows [args to pass to dot/neato...]"
echo "where nrows >= 3"
echo "typical dot args: -Tpng -o binarytree.png"
exit 1
else
rows=$1
shift
fi
treedata=$(sage -c 'execfile("BCLIB-sage");'\
'print("Result",[[[[0,0],[],1]]]+'\
'map(lambda k:map(lambda x:[[k,x],'\
'bpnorm(bptree([k,x])),bp2num(bpnorm(bptree([k,x])))],'\
'range(2^(k-1))),range(1,'"$rows"')))' |
fgrep "'Result'"|cut -d, -f2-|cut -d')' -f1)
expanded=$(echo "a=$treedata
"'print [["coord%s rep%s val:%d stop" % (p,q,r) for p,q,r in x] for x in a]'|
python)
halfparsed=$(
sed "s/'coord/\\n&/g;s/stop'/&\\n/g;s/[:[]/ &/g" <<< "$expanded"|
sed -n "s/, /,/g;/stop'/p")
nodes=$(
awk '{
gsub(/,/,".",$2);
gsub(/[][]/,"",$2);
print " " $2 " [label=\"" $4 $6 "\"];"}' <<<"$halfparsed")
gv1=$(echo -e 'digraph tree {\n node [shape=box];\n 0.0 -> 1.0;')
gv2=$(
r=2
while [ $r -lt $rows ]; do
cols=$(dc -e "2 $[ $r - 1 ] ^ p")
c=0
x=0
while [ $c -lt $cols ]; do
echo " $[ $r - 1].$(dc -e "0 k $c 2 / p") -> $r.$c"\
";"
#change previous line to the following to try attach-points for digraph
#"$(if [ $x -eq 0 ]; then echo ':ne'; else echo ':nw' ; fi);"
#in truth, it is harder to read, because the arrows curve and overlap---
#something I plan to fix
c=$[ $c + 1 ]
x=$[ 1 - $x ]
done
r=$[ $r + 1 ]
done
)
(echo "$gv1";echo "$gv2";echo "$nodes";echo "}")|dot "$@"
# see these for potential output tuning with graphviz 2.28:
# http://stackoverflow.com/questions/10902745/
# enforcing-horizontal-node-ordering-in-a-dot-tree
# https://mailman.research.att.com/pipermail/
# graphviz-interest/2010q2/007101.html
# the Ganser tree.gv script can be modified to work with graphviz 2.26.3
# by removing the second BEG_G section and changing TV_postfwd to TV_fwd
# in the first BEG_G section, but the output is not wide enough to
# prevent the nodes from overlapping (when I get a chance, I'll fix it)
# for now, the tree output is still pretty good, because it's a balanced
# and complete tree from the second row down
# this is how you might call the Ganser tree.gv script (if stored as
# ganser-tree.gv):
#(echo "$gv1";echo "$gv2";echo "$nodes";echo "}")|dot|
# gvpr -c -fganser-tree.gv|neato -n "$@"
And here's BCLIB-sage converted the same way:
# load with execfile(path)
def basep(n):
a=[]
if n>=2:
f=factor(n)
r=prime_range(1,f[len(f)-1][0]+1)
o=0
for i in range(len(r)):
#### print(i,r[i],o,f[o][0],f[o][1])
if f[o][0]==r[i]:
a.append(f[o][1])
o=o+1
else:
a.append(0)
return a
def bp2num(a):
if(len(a)):
p=[2]
while len(p)=len(a) else b[r]*a[x-r],range(w))
z=map(lambda a,b:a+b,z,y)
return bpnorm(z)
def bpconj(a):
if(len(a)):
if(a[0]):
c=[0,a[0]-1]+a[1:]
else:
c=[a[1]+1]+a[2:]
else:
c=[]
return c
def bptree(z):
r=z[0]
c=z[1]
p=[1,0]
o = map(lambda x:0,range(r))
for k in range(r):
print("@",k,":")
m = floor(c / 2);
m = m * 2
m = c - m
if m > 0:
print("R");
o[r - k - 1] = 0
c = floor((c - 1) / 2)
else:
print("L");
o[r - k - 1] = 1
c = floor(c / 2)
print(",c:=",c)
print(p)
for j in range(2, r + 1):
p.append(0);
print(o)
for k in range(len(o)):
print("op",k,o[k])
if o[k] > 0:
p[1] = p[1] + 1
else:
print("n",p[0])
print(p)
for j in range(p[0], 0, -1):
print("j",j,p[j])
p[j + 1] = p[j]
p[1] = 0
p[0] = p[0] + 1
print(p)
return p[1:]
def inbptree(p):
g = 1
o = []
while g>0:
if len(p)==1 and p[0]==0:
p=[]
if len(p)>0:
if p[0] > 0:
p[0] = p[0] - 1
o.append(1)
else:
for k in range(len(p)-1):
p[k] = p[k + 1]
p = p[0:len(p)-1]
o.append(0)
else:
g=0
r=0
c=0
for k in range(len(o)-1,-1,-1):
if o[k]>0:
r=r+1
c=c*2
else:
r=r+1
c=c*2+1
return (r,c)
Here's the output from ./baseprime-bintree 6 -Tpng -obinarytree.png
(view full size)