:

## Maple Iterators

Maple 16 introduces the ?ModuleIterator method, which can be assigned in a module so that it can be used  in a for-loop, or in the seq, add, and mul procedures.

ModuleIterator should return two procedures.  The first (referred to as hasNext) is a predicate that returns true if the iterator is not finished.  The second (referred to as getNext) returns the value of the next iteration.

Here is a quick example that assign a procedure, chars, that constructs a module that can be used to iterate over the characters in a given string.  This is a demonstration, not a practical example; there are better ways to do that.

`restart;chars := proc( s :: string )    module()    local ModuleIterator;        ModuleIterator := proc()        local cnt,len;            len := length(s);            cnt := 0;            ( proc() evalb(cnt < len) end proc,     # hasNext              proc() cnt := cnt+1; s[cnt]; end proc # getNext            );        end proc;    end module;end proc:L := chars("hello");                L := module() local ModuleIterator;  end modulefor c in L do printf("%a\n", c); end do:"h""e""l""l""o"seq(c, c = L);                            "h", "e", "l", "l", "o"`

Because an iterator returns elements one at a time, rather than all at once, it is possible to avoid allocating large chunks of memory.

The Iterator package, available at the Maple Application Center, provides constructors for iterators that iterate over typical finite structures: permutations, combinations, cartesian products, etc. By default the iterators are compiled.  The iterators reuse an Array as the output to avoid allocating additional memory with each iteration.  As such they are fast and efficient.

Here is a simple example that generates all partitions of 13 into 5 parts.

`with(Iterator):M := PartitionFixedSize(13,5):for v in M do printf("%d\n",v) end do:9 1 1 1 17 2 2 1 15 3 3 1 16 2 2 2 14 3 3 2 13 3 3 3 15 2 2 2 23 3 3 2 2`

Here is a more interesting example that uses the TopologicalSorts export to generate all solutions for a specified Young tableau.

Assign a procedure that returns an iterator and a formatter. The formatter is used to fill a Matrix so it represents the shape of the Young tableau.  The procedure's single parameter is a list that specifies, from top to bottom,  the length of each row of the tableau.

`Young := proc(shape::list(posint))local i,j,nmax,m,n,rels,Y,M,Format;    if not ListTools:-Sorted(shape, `>`) then        error "the first argument must be sorted in descending order";    end if;    nmax := add(i,i=shape);    # Create an mxn Matrix, M, that will be used for two purposes:    # (1) to create the relations passed to TopologicalSorts, and    # (2) to format the computed result.    m := nops(shape);    n := shape[1];    M := Matrix(m,n);    # Create a procedure that fills M with a given permutation.    # Cells not filled have 0.    Format := proc(V);    local i,j,k;        k := 0;        for i to nops(shape) do            for j to shape[i] do                k := k+1;                M[i,j] := V[k];            end do;        end do;        M;    end proc;    # Fill M sequentially.  This is used to generate the relations.    Format([seq(1..nmax)]);    rels := { NULL              , seq(seq(M[i,j]<M[i,j+1], j=1..n-1), i=1..m) # rows              , seq(seq(M[i,j]<M[i+1,j], i=1..m-1), j=1..n) # cols            };    rels := remove(has,rels,0);    # Construct the iterator    Y := Iterator:-TopologicalSorts(nmax, rels, 'inverse');    # Return the iterator and the formatter    return (Y,Format);end proc:(Y,F) := Young([3,2,1]):# Count the tableauxadd(1, v=Y);1 2 34 5 06 0 01 2 34 6 05 0 01 2 43 5 06 0 01 2 43 6 05 0 01 2 53 6 04 0 01 2 53 4 06 0 01 2 63 4 05 0 01 2 63 5 04 0 01 3 42 5 06 0 01 3 42 6 05 0 01 3 52 6 04 0 01 4 52 6 03 0 01 3 52 4 06 0 01 3 62 4 05 0 01 3 62 5 04 0 01 4 62 5 03 0 0`

Corrections

1. Updated the source code to 2.2.0, which adds the inverse option to the TopologicalSorts export. It is available at the App Center. Modified the call in Young (above) to pass inverse to TopologicalSorts.

﻿