Re: prograMing: generating trees
- To: mathgroup@smc.vnet.net
- Subject: [mg10769] Re: prograMing: generating trees
- From: "Xah" <xah@best.com>
- Date: Thu, 5 Feb 1998 00:58:18 -0500
- Organization: Venus & Xah Love Factory
- References: <6ahq8u$pnq@smc.vnet.net>
Here's the solution to last week's MinimumTreeGenerator challenge. (I
havn't got any reply) This solution is succinct, but I'm certain there
are many other approaches with exemplary implementation.
The definition of MinimumTreeGenerator uses FullIndexSet, which is
itself a useful function.
--
Clear[FullIndexSet];
FullIndexSet::"usage"=
"FullIndexSet[{index1,index2,...}] returns a complete tree index set
that \
is implied by the given indexes. Example:
FullIndexSet[{{3,3},{1,1},{7}}]";
FullIndexSet[indexes_List]:=
Composition[DeleteCases[#,{},{1}]&,Union,Flatten[#,1]&]@
Map[(FixedPointList[
Replace[#,{frest___,x_}:>If[x=!=0,{frest,x-1},{frest}]]&,#]&),
indexes];
Clear[MinimumTreeGenerator];
MinimumTreeGenerator::"usage"=
"MinimumTreeGenerator[{positionIndex1,positionIndex2,...}] generates a
\ minimum expression having given position indexes. 0 is used as the
atoms of \
the expression generated. Example: MinimumTreeGenerator[{{2,0,3},{5}}]";
MinimumTreeGenerator[indexes_List]:=
Fold[MapAt[If[Last@#2===0,(#[])&,Append[#,0]&],#1,{Drop[#2,-1]}]&,0,
Sort@FullIndexSet@indexes];
--
Here are some explainations of the code.
FullIndexSet algorithm description:
Suppose one of the given index is {a,b,c,d}. If the last digit is not 0,
then generate {a,b,c,d-1}. If the last digit is 0, then generate
{a,b,c}. Now repeat the steps on the result until the result no longer
changes, i.e. {}. Now do the above with every given index. Now take the
result and eliminate duplicates and {}. The result is as desired.
MinimumTreeGenerator Code explained: Start with a complete index set
implied by the given indexes. Sort them in standard way so that shallow
parts come first. These steps are generated by
Sort@FullIndexSet@indexes. For example, if input is {{2,0,3},{5}}, then
the sorted full index set is:
{{0},{1},{2},{3},{4},{5},{2,0},{2,0,0},{2,0,1},{2,0,2},{2,0,3}}. We then
build a tree with these indexes starting from the first index. This is
done by Fold, starting with the expression 0 and with subsequent
indexes as 2nd argument. Now, given an index {a,b,c}, if its last digit
is 0, then it means adding a new level at {a,b}. If the last digit is
not 0, then it means append a new element at {a,b}. These steps are
done with MapAt[If[Last@#2===0,(#[])&,Append[#,0]&],#1,{Drop[#2,-1]}]&.
--
Note the approach taken by MinimumTreeGenerator: it generates a full
index set first, then use these indexes to build the tree. I'd be very
interested to see a solution that does not generate the full indexes as
an intermediate step, but rather generate the tree directly from a
given index, perhaps using recursive methods. I don't know if the
explicit use of full indexes can be avoided.
Also, the code for FullIndexSet is not without possible improvements.
For instance, it involves deleting dulplicates and empty braces, which
I deem undesirable. Can you come up a better solution?
Xah, xah@best.com
http://www.best.com/~xah/Wallpaper_dir/c0_WallPaper.html
"I don't ask for much... all I want is a little drink now and then."