, <real step>)combinat::generators – generators
The library combinat::generators provides functions for producing and manipulating generators.
Details:
A generator is a device that allows for iterating over a large or even infinite quantity of objects, without having to produce and store all of them at once. This is typically very handy in combinatorics.
In principle a generator is any MuPAD object g such that the function call g() is defined. Each call g() returns either the next object, or FAIL if no more objects are available. The effect of calling g() after the FAIL value has been returned is undefined (i.e. possibly disastrous).
Entries
|
"empty" |
The empty generator, iterating over the empty set |
count – number of elements generated by a generator
combinat::generators::count(generator g)
Returns the number of elements generated by g.
accumulate – accumulate the elements generated by a generator
combinat::generators::accumulate(generator g)
combinat::generators::accumulate(generator g, <start, function accumulator>)
Returns the sum of the elements generated by g.
Starts from r:=start, and accumulate each element e generated by g with r := accumulator(r,e). Finally, returns r.
toList – list of the elements generated by a generator
combinat::generators::toList(generator g)
Returns the list of the elements generated by g.
See also combinat::generators::fromList.
singleton – generator for a single value
combinat::generators::singleton(value)
Returns a generator which produce value once and then fails.
repeater – generator repeating a value
combinat::generators::repeater(value)
combinat::generators::repeater(value, nonnegative integer n)
Returns a generator repeating value forever.
Returns a generator repeating valuen times.
fromRange – generator from range
combinat::generators::fromRange(range , <real step>)
Returns a generator iterating over the elements in the range i..j. An optional parameter rstep may be given to iterate through i, i+rstep, ..., i+k*rstep. Negative rstep are allowed, with the natural semantic.
fromList – generator from list
combinat::generators::fromList(list l)
Returns a generator iterating over the elements of the list l.
See also combinat::generators::toList.
fromNext – generator from first value and next operation
combinat::generators::fromNext(first, function fnext)
Returns a generator iterating over the sequence first, fnext(first),fnext(fnext(first)), ... The function fnext must return FAIL if there is no next object.
fromUnrank – generator from unrank function
combinat::generators::fromUnrank(unrank fuonction f, <options>)
Returns a generator iterating over the sequence f(1, options), f(2, options), f(3, options), ... If f(r, options) is not defined for large r the function f must return FAIL for such r.
map – application of a function on a generator
combinat::generators::map(generator g, function f)
Returns a generator iterating over the images by f of the elements generated by g.
compose – composition of a generator and a function
combinat::generators::compose(function f, generator g)
Returns a generator iterating over the images by f of the elements generated by g (deprecated; please use the equivalent function combinat::generators::map).
select – generator filter
combinat::generators::select(generator g, predicate f, <options>)
Returns a generator iterating over the elements e generated by g which satisfy the criterion f(e, options).
concat – concatenation of generators
combinat::generators::concat(<generator g1>, <generator g2>, <
, generator gk>)
Returns a generator iterating over the elements generated successively by the generators g1, g2, ..., gk.
cartesian – cartesian product of generators
combinat::generators::cartesian(<generator g1>, <generator g2>, <
, generator gk>)
Returns a generator iterating over the lists [e1,e2,...,ek] where e1,e2,...,ek are elements generated respectively by g1,g2,...,gk.
cartesianPower – cartesian power product of a generator
combinat::generators::cartesianPower(generator g, non negative integer k)
Returns a generator iterating over the lists [e1,e2,...,ek] of 
elements generated by g.
multiset – multiset of a generator
combinat::generators::multiset(generator g, non negative integer k)
Returns a generator iterating over the multisets {{e1,e2,...,ek}} of elements generated by g.
powerset – powerset of a generator
combinat::generators::powerset(generator g, non negative integer k)
Returns a generator iterating over the sets {e1,e2,...,ek} of elements generated by g.
pipe – composition of a generators and a generator constructor
combinat::generators::pipe(generator g, generator constructor 
, <options>)
Returns the concatenation of the generators constructed by successive calls of construct(g(), options).
copy – copy of a generator
combinat::generators::copy(generator g)
Returns a copy of the generator g. The copy is a generator which gives the same result as g, but is independent (no reference effect). Calling g does not affect the copy and conversely.
We demonstrate how to construct simple generators. The empty generator iterates over the empty set, and thus returns FAIL immediately:
g := combinat::generators::empty:
g()
The following generator repeats a forever:
g := combinat::generators::repeater(a):
g(), g(), g(), g(), g()
This one repeats a three times:
g := combinat::generators::repeater(a, 3):
g(), g(), g(), g()
We build a generator which iterates over the elements of the list [a,b,c]:
g := combinat::generators::fromList([a,b,c]):
g(), g(), g(), g()
Here is a generator iterating over the range -1..2:
g := combinat::generators::fromRange(-1..2):
g(), g(), g(), g(), g()
The same generator, going down:
g := combinat::generators::fromRange(2..-1, -1):
g(), g(), g(), g(), g()
We build a generator using the natural recursive definition of nonnegative integers:
g := combinat::generators::fromNext(0, n->n+1):
g(), g(), g(), g(), g(), g()
Another way to do that is to use an unranking function:
g := combinat::generators::fromUnrank((n)->n-1):
g(), g(), g(), g(), g(), g()
Here is a way to define a generator for lists of length 
with 
zeros and only one 
.
n := 5:
g := combinat::generators::fromUnrank(
(x, len) -> if x <= len then [0$(x-1), 1, 0$(len-x)]
else FAIL end_if, n):
g(), g(), g(), g(), g(), g()
Generators can be modified in different ways. With combinat::generators::map one can apply a function on the elements generated. Here is a generator for the squares of nonnegative integers:
g := combinat::generators::map(
combinat::generators::fromNext(0, n->n+1),
n->n^2
):
g(), g(), g(), g(), g(), g()
combinat::generators::select is handy to pick out the elements generated which satisfy a criterion. Here is a brute-force generator for prime numbers:
g := combinat::generators::select(
combinat::generators::fromNext(0, n->n+1),
isprime):
g(), g(), g(), g(), g(), g()
Beware of infinite loops when selecting elements out of an infinite generator. Here is a brain-dead generator for the positive integers less or equal to 
:
g := combinat::generators::select(
combinat::generators::fromNext(1, n->n+1),
_leequal, 5):
g(), g(), g(), g(), g()
Calling g() once more would not terminate!
Generators can be combined together. This is a generator for the union of the ranges 1..3 and 7..8:
g := combinat::generators::concat(
combinat::generators::fromRange(1..3),
combinat::generators::fromRange(7..8)):
g(), g(), g(), g(), g(), g()
This is a generator for the cartesian product of the ranges 1..3 and 7..8:
g := combinat::generators::cartesian(
combinat::generators::fromRange(1..3),
combinat::generators::fromRange(7..8)):
g(), g(), g(), g(), g(), g(), g()
combinat::generators::pipe allows for concatenating a series of similar generators which are constructed on the fly from the successive result of another generator. Here is a generator for the sequence 1,2,2,3,3,3,...:
g := combinat::generators::pipe(
combinat::generators::fromNext(0, n->n+1),
n->combinat::generators::repeater(n,n)):
g(), g(), g(), g(), g(), g(), g(), g(), g(), g(), g()
Typically, this can be used for building a generator for all integer partitions, size by size:
g := combinat::generators::pipe(
combinat::generators::fromNext(0, n->n+1),
combinat::partitions::generator):
g(), g(), g(), g(), g(), g(), g(), g(), g(), g(), g(), g(), g(), g()
We demonstrate how to construct your own generators. To define a non-constant generator g, we need to modify the internal state of the object g. Due to the default copy-semantic of MuPAD (no reference effect, see copyClosure), this is impractical with most objects. The only exceptions to this rule are closures, domains (not domain elements!), and objects defined in dynamic modules.
The easiest way to define a generator in MuPAD is to use closures. Here is a generator for the sequence 1^3,2^3,3^3,4^3:
power_generator :=
proc(k)
local i;
option escape;
begin
i := 0;
proc() begin i := i+1; i^k; end_proc
end_proc:
g := power_generator(3):
g(), g(), g(), g(), g()
What happens here is that the variable i in the procedure g returned by power_generator is lexically bound to the context of power_generator (note the option escape). Hence, its value is persistent across successive calls of g.
Generators, as all closures, display a reference effect:
g := combinat::generators::fromNext(1, n->n+1):
g(), g();
h := g:
g(), g();
h(), h();
g(), g()
This effect also appears when passing a generator as argument to a function:
g := combinat::generators::fromNext(1, n->n+1):
consume := proc(g) begin g(); end_proc:
g(), g();
consume(g), consume(g);
g(), g()
This reference effect can be broken by making a full copy of the generator with the method combinat::generators::copy:
g := combinat::generators::fromNext(1, n->n+1):
g(), g();
h := combinat::generators::copy(g):
g(), g();
h(), h();
g(), g()
Note that this does not work for all generators (see background):
g := combinat::generators::fromNext(1, n->n+1):
h := proc() begin g(); g(); end_proc:
h(), h();
h2 := combinat::generators::copy(h):
h(), h();
h2(), h2();
h(), h()
Background:
In practice, most generators are closures, of type DOM_PROC.
Most of the generators built with MuPAD-combinat can be copied via "copy", including generators with embedded generators such as those constructed with combinat::generators::cartesian, "select", "compose", "concat", "cartesian", "map", and "pipe". Simple closures without embedded generator are readily copyable. There exists an undocumented tool to construct more complicated copyable generators; however the interface is still in design.