[Previous] [Next] [Contents]

combinat::generators -- generators

Introduction

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

Details

Entries

empty

The empty generator, iterating over the empty set

Method count: number of elements generated by a generator

Method toList: list of the elements generated by a generator

Method repeater: generator repeating a value

Method fromRange: generator from range

Method fromList: generator from list

Method fromNext: generator from first value and next operation

Method fromUnrank: generator from unrank function

Method map: application of a function on a generator

Method compose: composition of a generator and a function

Method select: generator filter

Method concat: concatenation of generators

Method cartesian: cartesian product of generators

Method pipe: composition of a generators and a generator constructor

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

[Previous] [Next] [Contents]


MuPAD Combinat, an open source algebraic combinatorics package