MinimumTreeGenerator

By Xah Lee. Date:

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?

2005-09

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