# TreeGenerator

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}, for example, {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!

If you have a question, put $5 at patreon and message me.