|
Calling Sequence
|
|
BinaryTrees(n, opts)
|
|
Parameters
|
|
n
|
-
|
nonnegint; number of internal nodes of a binary tree
|
opts
|
-
|
(optional) equation(s) of the form option = value; specify options for the BinaryTrees command
|
|
|
|
|
Options
|
|
|
True means compile the iterator. The default is true.
|
|
Specify the starting rank of the iterator. The default is one. Passing a value greater than one causes the iterator to skip the lower ranks; this can be useful when parallelizing iterators. 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, and , each indexed from 1 to n. Their elements define the connections for the left and right branches, respectively. is the node to which the left-branch of node connects. If is 0 then it is connected to an external (terminal) node. 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
|
|
Construct an iterator over binary trees with four internal nodes. In the loop, lr is assigned a sequence of two Arrays, .
>
|
|
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.
>
|
|
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.
|
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.
((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
| |
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:
|
((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
| |
|
|
|
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.
|
•
|
The Iterator[BinaryTrees] command was updated in Maple 2022.
|
•
|
The n parameter was updated in Maple 2022.
|
|
|
|