Iterator - Maple Programming Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Discrete Mathematics : Combinatorics : Iterator : Iterator/BinaryTrees

Iterator

  

BinaryTrees

  

generate binary trees of a given size

 

Calling Sequence

Parameters

Options

Description

Examples

References

Compatibility

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. Lk is the node to which the left-branch of node k connects. If Lk 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

The 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

withIterator:

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

BBinaryTrees4:

forlrinBdoprintf%d - %d\n,lrenddo

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.

NumberB

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 arithmentic 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.

DigitalPuzzle6

((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:

DigitalPuzzle26

((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.

• 

For more information on Maple 2016 changes, see Updates in Maple 2016.

See Also

Iterator

Iterator[NestedParentheses]