[Previous] [Next] [Contents]

## `combinat::generators` -- generators

#### Introduction

The library `combinat::generators` provides functions for producing and manipulating generators.

#### Details

- A generator is a device that allow 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 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).

#### Entries

empty

The empty generator, iterating over the empty set

#### Method count: number of elements generated by a generator

- `count(generator g)`

- Returns the number of elements generated by `g`.

#### Method toList: list of the elements generated by a generator

- `toList(generator g)`

- Returns the list of the elements generated by `g`.
- See also `combinat::generators::fromList`.

#### Method repeater: generator repeating a value

- `repeater(value)`

- Returns a generator repeating `value` forever.

- `repeater(value, nonnegative integer n)`

- Returns a generator repeating `value` `n` times.

#### Method fromRange: generator from range

- `fromRange(range i..j)`

- Returns a generator iterating over the elements in the range `i..j`.

#### Method fromList: generator from list

- `fromList(list l)`

- Returns a generator iterating over the elements of the list `l`.
- See also `combinat::generators::toList`.

#### Method fromNext: generator from first value and next operation

- `fromNext(first, function next)`

- Returns a generator iterating over the sequence `first, next(first)`,
  next(next(first))... The function `next` must return `FAIL` if there is no next object.

#### Method fromUnrank: generator from unrank function

- `fromUnrank(unrank fonction 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`.

#### Method map: application of a function on a generator

- `map(generator g, function f)`

- Returns a generator iterating over the images by `f` of the elements generated by `g`.

#### Method compose: composition of a generator and a function

- `compose(function f, generator g)`

- Returns a generator iterating over the images by `f` of the elements generated by `g` (please use the equivalent function `combinat::generators::map`).

#### Method select: generator filter

- `select(generator g, predicate f, <options>)`

- Returns a generator iterating over the elements `e` generated by `g` which satisfy the criterion `f(e, options)`.

#### Method concat: concatenation of generators

- `concat( <generator g1> <, generator g2> <, ..., generator gk>)`

- Returns a generator iterating over the elements generated successively by the generators `g1, g2, ..., gk`.

#### Method cartesian: cartesian product of 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`.

#### Method pipe: composition of a generators and a generator constructor

- `pipe(generator g, generator constructor construct <, options>)`

- Returns the concatenation of the generators constructed by successive calls of `construct(g(), options)`.

#### Example 1

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

#### Example 2

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!

#### Example 3

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]

#### Example 4

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

#### Example 5

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

#### Background

- In practice, most generators are closures, of type `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.

[Previous] [Next] [Contents]

MuPAD Combinat, an open source algebraic combinatorics package