Binary Trees - Maple Help

Iterator

 BinaryTrees
 generate binary trees of a given size

 Calling Sequence BinaryTrees(n, opts)

Parameters

 n - posint; number of internal nodes of a binary tree opts - (optional) equation(s) of the form option = value; specify options for the BinaryTrees command

Options

 • compile = truefalse
 True means compile the iterator. The default is true.
 • rank = nonnegint
 Specify the starting rank of the iterator. The default is one. The starting rank reverts to one when the iterator is reset, reused, or copied.

Description

 • The BinaryTrees command returns an iterator that generates all binary trees with n internal nodes.
 • The getNext method of the ModuleIterator returns two Arrays, $L$ and $R$, each indexed from 1 to n.  Their elements define the connections for the left and right branches, respectively. ${L}_{k}$ is the node to which the left-branch of node $k$ connects. If ${L}_{k}$ is 0 then it is connected to an external (terminal) node.  $R$ is similarly defined for the right-branches.
 • See Iterator[Trees] for procedures to convert this format (LR) to other formats for nested parentheses and binary trees.

Methods

In addition to the common iterator methods, this iterator object has the following methods. The self parameter is the iterator object.

 • Number(self): return the number of iterations required to step through the iterator, assuming it started at rank one.
 • Rank(self,L): return the rank of the current iteration. Optionally pass L, a list or one-dimensional rtable, and return its rank.
 • Unrank(self,rnk): return a one-dimensional Array corresponding to the iterator output with rank rnk.

Examples

 > $\mathrm{with}\left(\mathrm{Iterator}\right):$

Construct an iterator over binary trees with four internal nodes. In the loop, lr is assigned a sequence of two Arrays, $L,R$.

 > $B≔\mathrm{BinaryTrees}\left(4\right):$
 > $\mathbf{for}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathrm{lr}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{in}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}B\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{2.0em}{0.0ex}}\mathrm{printf}\left("%d - %d\n",\mathrm{lr}\right)\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\mathbf{end}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{do}$
 2 3 4 0 - 0 0 0 0 0 3 4 0 - 2 0 0 0 2 0 4 0 - 0 3 0 0 2 0 4 0 - 3 0 0 0 0 0 4 0 - 2 3 0 0 2 3 0 0 - 0 0 4 0 0 3 0 0 - 2 0 4 0 2 3 0 0 - 0 4 0 0 2 3 0 0 - 4 0 0 0 0 3 0 0 - 2 4 0 0 2 0 0 0 - 0 3 4 0 2 0 0 0 - 4 3 0 0 2 0 0 0 - 3 0 4 0 0 0 0 0 - 2 3 4 0

Use the Print method to do the same, and show the rank.

 > $\mathrm{Print}\left(B,'\mathrm{showranks}'\right):$
 2 3 4 0 - 0 0 0 0 0 3 4 0 - 2 0 0 0 2 0 4 0 - 0 3 0 0 2 0 4 0 - 3 0 0 0 0 0 4 0 - 2 3 0 0 2 3 0 0 - 0 0 4 0 0 3 0 0 - 2 0 4 0 2 3 0 0 - 0 4 0 0 2 3 0 0 - 4 0 0 0 0 3 0 0 - 2 4 0 0 2 0 0 0 - 0 3 4 0 2 0 0 0 - 4 3 0 0 2 0 0 0 - 3 0 4 0 0 0 0 0 - 2 3 4 0

Compute the number of iterations.

 > $\mathrm{Number}\left(B\right)$
 ${14}$ (1)

Dudney's Century Puzzle

Dudney's Digital Century puzzle consists of finding all parenthesized arithmetic expressions on the digits 1 to 9, in that order, that equal 100. For example, 1 + ((((((2 - 3) - 4) - 5) + 6) + 7) + 8) * 9 = 100. A simplified version of this puzzle, sans parentheses, is presented in the examples of the BinaryGrayCode command.

An arithmetic expression can be represented as a binary tree, with the internal nodes corresponding to arithmetic operations and the leaves the numeric values.  We can use BinaryTrees to loop through all binary trees with 9 leaves (equivalently, 8 internal nodes), and then use MixedRadixTuples in an inner loop to vary the contents of the internal nodes.  To prevent trees with trivially distinct branches consisting of, say, 1 + (2 + 3) and (1 + 2) + 3, reject any tree with a right branch that consists of connected additive operators (+ and -) or connected multiplicative operators (* and /).

The principal challenge is to make this reasonably efficient. The method used here is to convert a binary tree to a Maple expression in infix form, with the functions represented by indexed names that are then replaced with the actual arithmetic operations.  This avoid walking the tree for each of the 4^8 inner loops.

Assign an appliable module that solves the puzzle. The first argument, n, is the number of internal nodes.

 > DigitalPuzzle := module() export ModuleApply; local Expr, Print;     # Given the L and R Arrays from the BinaryTree iterator,     # construct an expression corresponding to the tree,     # where o[v[i]] is the arithmetic operator of the i-th     # internal node (the v-Array is used to change the operators     # for a given tree).     Expr := proc(L,R)     local leaf,prefix;     global o,v;         leaf := 0;         prefix := proc(i)             if i=0 then leaf := leaf+1;             else 'o'['v'[i]](prefix(L[i]),prefix(R[i]));             end if;         end proc;         prefix(1);     end proc:     # Given the L and R arrays of the current tree, and an array, v,     # that maps the internal nodes to the arithmetic operators (stored     # in o), print a string corresponding to the desired equality.     # Avoid most superfluous parentheses.     Print := proc(L,R,v,o,targ)     local leaf,infix,top;         leaf := 0;         top := true;         infix := proc(i)             if i=0 then leaf := leaf+1;             elif top then                 top := false;                 sprintf("%A %A %A", infix(L[i]), o[v[i]], infix(R[i]));             elif v[i]=2 then                 sprintf("%A %A %A", infix(L[i]), o[v[i]], infix(R[i]));             else                 sprintf("(%A %A %A)", infix(L[i]), o[v[i]], infix(R[i]));             end if;         end proc;         printf("%s = %a\n", infix(1), targ);     end proc:     ModuleApply := proc(n::posint, targ:=100)     local A,Accept,cnt,ops,Op,BT,LR,R,s;     uses Iterator;         # Array of arithmetic operators         ops := Array(0..3,[+,-,*,/]);         # Template for the accept predicate.         Accept := proc(v,o:=ops)         local j;             # Prune trees with a right branch that connects             # two additive or two multiplicative operators.             for j to n do                 if R[j]<>0 and (v[j] <= 1 xor v[R[j]] > 1) then                     return false;                 end if;             end do;             # Use try/catch to handle division by zero.             try                 evalb(_ex=targ);             catch:                 false;             end try;         end proc;         # Construct an iterator that generates all possible values of         # arithmetic operators (as an Array with values from 0 to 3         # corresponding to the four operations), but accepts (outputs)         # only those that meet the criteria.         Op := MixedRadixTuples([4$n]); # Construct an iterator that generates all binary trees # with n-internal nodes (and n+1 leaves). BT := BinaryTrees(n); cnt := 0; # success counter # Loop through all binary trees for LR in BT do R := LR[2]; # Assign A, by specializing Accept to the # selected tree. A := subs('_ex'=Expr(LR),op(Accept)); # Loop through all possibilities of assigning # the arithmetic operators to the internal nodes of the # tree, keeping only those that evaluate to the target. for s in Op do if A(s) then cnt := cnt+1; Print(LR,s,ops,targ); end if; end do; end do; cnt; end proc: end module: The full puzzle takes a while to solve. Here we solve the puzzle for n equal to 6, which uses the digits 1 to 7.  > $\mathrm{DigitalPuzzle}\left(6\right)$  ((1 + (2 + 3) * 4 * 5) + 6) - 7 = 100 ((1 - 2) + 3) + (4 * 5 - 6) * 7 = 100 (1 - 2 * 3) + ((4 + 5) + 6) * 7 = 100 1 * 2 * ((3 + (4 + 5) * 6) - 7) = 100 (1 + 2 * 3 * 4) * ((5 + 6) - 7) = 100 (1 - 2 * 3) * 4 * 5 * (6 - 7) = 100 (1 - 2 * 3) * 4 * 5 / (6 - 7) = 100  ${7}$ (2) Here is an alternative approach that uses a compiled procedure to evaluate a flattened version of each tree. It a bit less than twice as fast.  > DigitalPuzzle2 := module() export ModuleApply, Accept, Flatten; local Print; # Given the L and R arrays from the BinaryTrees iterator, # flatten the tree into postfix form. The result is # stored in the one-dimensional Array Data. # The leaves are represented as the corresponding integer, # the internal nodes as the negative of the node number. Flatten := proc(L :: Array(datatype=integer[4]) , R :: Array(datatype=integer[4]) , Data :: Array(datatype=integer[4]) , n :: posint ) local leaf,postfix,node,data; leaf := 0; postfix := proc(node) if node=0 then leaf := leaf+1; else ( procname(L[node]), procname(R[node]), -node ); end if; end proc; data := [postfix(1)]; for node to 2*n+1 do Data[node] := data[node]; end do; NULL; end proc; # Given the R array from BinaryTree iterator and the flattened # tree structure (Data), from Flatten, and the array, Ops, holding # the arithmetic operations, coded as 0=+, 1=-, 2=*, 3=/, for each # of the internal nodes, return true if the tree equals the target # value, targ. This routine will be compiled. The Stack argument # is used as a working stack. Accept := proc( R :: Array(datatype=integer[4]) , Data :: Array(datatype=integer[4]) , Stack :: Array(datatype=float[8]) , Ops :: Array(datatype=integer[4]) , n :: posint , targ :: float ) local ptr :: integer , node :: integer , datum :: integer , l :: float , r :: float , f :: integer , val :: float ; # Prune trees with a right branch that connects # two additive or two multiplicative operators. for node to n do if R[node]<>0 and (Ops[node] <= 1 xor Ops[R[node]] > 1) then return false; end if; end do; # Evaluate the flattened tree ptr := 0; for node to 2*n+1 do datum := Data[node]; if datum > 0 then # datum is a leaf value. Push onto stack. ptr := ptr+1; Stack[ptr] := datum; else # -datum is an internal node number; # internal nodes correspond to arithmetic operations. # Pop the top two elements off the stack, # compute the result, and push onto the stack. r := Stack[ptr]; ptr := ptr-1; l := Stack[ptr]; f := Ops[-datum]; if f = 0 then Stack[ptr] := l + r; elif f = 1 then Stack[ptr] := l - r; elif f = 2 then Stack[ptr] := l * r; else Stack[ptr] := l / r; end if; end if; end do; # Test whether the computed value matches the target. val := Stack[1]; if abs(val - targ) < 1e-6 then return true; else return false; end if; end proc; Accept := Compiler:-Compile(Accept); # Given the L and R arrays of the current tree, and an array, v, # that maps the internal nodes to the arithmetic operators (stored # in o), print a string corresponding to the desired equality. Print := proc(L,R,v,o,targ) local leaf,infix,top; leaf := 0; top := true; infix := proc(i) if i=0 then leaf := leaf+1; elif top then top := false; sprintf("%A %A %A", infix(L[i]), o[v[i]], infix(R[i])); elif v[i]=2 then sprintf("%A %A %A", infix(L[i]), o[v[i]], infix(R[i])); else sprintf("(%A %A %A)", infix(L[i]), o[v[i]], infix(R[i])); end if; end proc; printf("%s = %a\n", infix(1), targ); end proc: ModuleApply := proc(n::posint, targ:=100) local Data , Stack , cnt,ops,Op,BT,LR,R,V; uses Iterator; # Array of arithmetic operators ops := Array(0..3,[+,-,*,/]); # Construct an iterator that generates all possible values of # arithmetic operators (as an Array with values from 0 to 3 # corresponding to the four operations), but accepts (outputs) # only those that meet the criteria. Op := MixedRadixTuples([4$n]);         # Construct an iterator that generates all binary trees         # with n-internal nodes (and n+1 leaves).         BT := BinaryTrees(n);         Data := Array(1..2*n+1, 'datatype'=integer[4]);         Stack := Array(1..2*n+1, 'datatype'=float[8]);         cnt := 0; # success counter         # Loop through all binary trees         for LR in BT do             # Assign Data the flattened structure of the tree             Flatten(LR,Data,n);             R := LR[2];             # Loop through all possibilities of assigning             # the arithmetic operators to the internal nodes of the             # tree             for V in Op do                 if Accept(R,Data,Stack,V,n,targ) then                     cnt := cnt+1;                     Print(LR,V,ops,targ);                 end if;             end do;         end do;         cnt;     end proc: end module:
 > $\mathrm{DigitalPuzzle2}\left(6\right)$
 ((1 + (2 + 3) * 4 * 5) + 6) - 7 = 100 ((1 - 2) + 3) + (4 * 5 - 6) * 7 = 100 (1 - 2 * 3) + ((4 + 5) + 6) * 7 = 100 1 * 2 * ((3 + (4 + 5) * 6) - 7) = 100 (1 + 2 * 3 * 4) * ((5 + 6) - 7) = 100 (1 - 2 * 3) * 4 * 5 * (6 - 7) = 100 (1 - 2 * 3) * 4 * 5 / (6 - 7) = 100
 ${7}$ (3)

References

 Knuth, Donald Ervin. The Art of Computer Programming, volume 4, fascicle 4; generating all trees, p. 6, algorithm B.

Compatibility

 • The Iterator[BinaryTrees] command was introduced in Maple 2016.