combinat::generators
--
generators
The library combinat::generators
provides functions for producing and
manipulating generators.
g
such that the
function call g()
is defined. Each call g()
returns either a
new 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).The empty generator, iterating over the empty set
count(generator g)
g
.
toList(generator g)
g
.combinat::generators::fromList
.
repeater(value)
value
forever.repeater(value, nonnegative integer n)
value
n
times.
fromRange(range i..j)
i..j
.
fromList(list l)
l
.combinat::generators::toList
.
fromNext(first, function next)
first,
next(first)
,next
must
return FAIL
if there is no next object.
fromUnrank(unrank fonction f, <options>)
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(generator g, function f)
f
of
the elements generated by g
.
compose(function f, generator g)
f
of
the elements generated by g
(please use the equivalent
function combinat::generators::map
).
select(generator g, predicate f, <options>)
e
generated by g
which satisfy the criterion
f(e, options)
.
concat( <generator g1> <, generator g2>
<, ..., generator gk>)
g1, g2, ..., gk
.
cartesian( <generator g1> <, generator g2>
<, ..., generator gk>)
[e1,e2,...,ek]
where e1,e2,...,ek
are elements
generated respectively by g1,g2,...,gk
.
pipe(generator g, generator constructor construct
<, options>)
construct(g(), options)
.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()
FAIL
The following generator repeats a
forever:
>> g := combinat::generators::repeater(a):
g(), g(), g(), g(), g()
a, a, a, a, a
This one repeats a
three times:
>> g := combinat::generators::repeater(a, 3):
g(), g(), g(), g()
a, a, a, FAIL
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()
a, b, c, FAIL
Here is a generator iterating over the range -1..2
:
>> g := combinat::generators::fromRange(-1..2):
g(), g(), g(), g(), g()
-1, 0, 1, 2, FAIL
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()
0, 1, 2, 3, 4, 5
Another way to do that is to use an unranking function:
>> g := combinat::generators::fromUnrank((n)->n-1):
g(), g(), g(), g(), g(), g()
0, 1, 2, 3, 4, 5
Here is a way to define a generator for lists of length n with n-1 zeros and only one 1.
>> 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()
[1, 0, 0, 0, 0], [0, 1, 0, 0, 0], [0, 0, 1, 0, 0], [0, 0, 0, 1, 0], [0, 0, 0, 0, 1], FAIL
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()
0, 1, 4, 9, 16, 25
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()
2, 3, 5, 7, 11, 13
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 5:
>> g := combinat::generators::select(
combinat::generators::fromNext(1, n->n+1),
_leequal, 5):
g(), g(), g(), g(), g()
1, 2, 3, 4, 5
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()
1, 2, 3, 7, 8, FAIL
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()
[1, 7], [1, 8], [2, 7], [2, 8], [3, 7], [3, 8], FAIL
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()
1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5
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()
[], [1], [2], [1, 1], [3], [2, 1], [1, 1, 1], [4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1], [5], [4, 1]
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()
1, 8, 27, 64, 125
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()
1, 2 3, 4 5, 6 7, 8
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()
1, 2 3, 4 5, 6
This reference effect can be avoided by taking a full copy of the
closure with copyClosure
note that this works not for all generators
(see the note in the background section):
>> g := combinat::generators::fromNext(1, n->n+1):
g(), g();
h := copyClosure(g):
g(), g();
h(), h();
g(), g()
1, 2 3, 4 3, 4 5, 6
DOM_PROC
(see
copyClosure
).Most of the generator can be copied via copyClosure
but
this is not sure. Thus for the moment generators cannot be copied.
In a near future, a working copy methods should be adder, but this forces
to complicate a little bit the structure of generators. In the midterm,
generator::cartesian
is implemented is a very crude way by expanding
the lists of the given generators.
MuPAD Combinat, an open source algebraic combinatorics package