prograMing: generating trees
- To: mathgroup@smc.vnet.net
- Subject: [mg10645] prograMing: generating trees
- From: "Xah" <xah@best.com>
- Date: Tue, 27 Jan 1998 03:10:09 -0500
- Organization: Venus & Xah Love Factory
Here's another recreational programing problem related to trees.
In this message, I'll give an example of a function that does certain
things, and will ask readers to write a similar function for which I
don't have a solution ready. (and am interested to see creativity from
readers of this group.)
TreeGenerator[positionIndex,Heads->True] returns an expression having
all parts up to positionIndex. Suppose positionIndex is {2,3,1}, then
the result will contain parts having position index of
{0,0,0}<={i,j,k}<={2,3,1}, e.g. {1,3}, {2,2,2}, {2,0,1}...etc. The
option Heads->False will ignore all 0s in positionIndex. 0 is used as
the Atom in the resulting tree.
For example, TreeGenerator[{2,2},Heads->False] returns 0[0[0,0],0[0,0]],
which is an expression having indexes
{0},{1},{2},{1,0},{1,1},{1,2},{2,0},{2,1}, and {2,2}. Now,
TreeGenerator[{2,2},Heads->True] returns 0[0,0][0[0,0],0[0,0]]. And the
indexes contained in that expression are:
In[29]:=
Position[0[0,0][0[0,0],0[0,0]],_,Infinity,Heads->True] Out[29]=
{{0,0},{0,1},{0,2},{0},{1,0},{1,1},{1,2},{1},{2,0},{2,1},{2,2},{2}}
Here is a recursive and an iterative implementation of TreeGenerator.
---------
Clear[TreeGenerator,TreeGenerator2]; TreeGenerator::"usage"=
"TreeGenerator[{i1,i2,...},(Heads->False)] generates an expression
having \
all parts up to position index {i1,i2,...}. If Heads->False, all indexes
that \
have value 0 are ignored. Example: \
Position[TreeGenerator[{2,0,2},Heads->True],_]";
(*Recursive version*)
TreeGenerator[d_List]:=TreeGenerator[d,Heads->False];
TreeGenerator[{},Heads->True]:=0;
TreeGenerator[{0,rest___},Heads->True]:=TreeGenerator[{rest},Heads->True][];
TreeGenerator[{a_,rest___},Heads->True]:=
TreeGenerator[{rest},Heads->True]@@
Table[TreeGenerator[{rest},Heads->True],{a}];
TreeGenerator[{},Heads->False]:=0;
TreeGenerator[{0,rest___},Heads->False]:=TreeGenerator[{rest},Heads->False];
TreeGenerator[{a_,rest___},Heads->False]:=
0@@Table[TreeGenerator[{rest},Heads->False],{a}];
(*Iterative version*)
TreeGenerator[d_List]:=TreeGenerator[d,Heads->False];
TreeGenerator[d_List,Heads->True]:=
Module[{i=Length@d,g},g=0;
Do[pos=Abs@d[[i]];If[pos===0,g=g[],g=g@@Table[g,{pos}]];--i,{i}];g];
TreeGenerator[d_List,Heads->False]:=
Module[{i=Length@d,g},g=0;
Do[pos=Abs@d[[i]];If[pos===0,Null,g=0@@Table[g,{pos}]];--i,{i}];g];
--------
The following snippet will let you test the versions. Suppose one of the
version is named TreeGenerator2.
Clear[opt];
And@@((TreeGenerator[#,opt=Heads->(Random[]>.5)]===TreeGenerator2[#,opt]&)/@
Table[Random[Integer,{0,3}],{200},{Random[Integer,{0,3}]}])
Notice that TreeGenerator does not generate a minimum tree for a given
positionIndex. For example, given an index {2,2}, TreeGenerator will
generate elements at {1,1} and {1,2}, which are not really necessary
for a tree to have an index at {2,2}.
The challenge is to write a MinimumTreeGenerator with the following
spec:
MinimumTreeGenerator::"usage"="MinimumTreeGenerator[{positionIndex},(Heads->
False)] generates a minimum expression having position index
positionIndex. If Heads->False, all indexes in positionIndex that have
value 0 are ignored.
MinimumTreeGenerator[{positionIndex1,positionIndex2,...},(opt)] returns
a minimum tree having elements at the specified indexes.";
I'm looking for exemplary codes with or without speed considerations.
Have fun!
PS I'll be posting a solution in about a week, if no solutions come up.
This problem seems to be a good candidate as a snippet in the
Mathematica Journal.
Xah, xah@best.com
http://www.best.com/~xah/Wallpaper_dir/c0_WallPaper.html
Perl side effects: make one assignment, the next thing you know your
house is deleted.