[Previous] [Next] [Contents]

Cat::CombinatorialClass -- the category of combinatorial classes

Introduction

Cat::CombinatorialClass represents the category of combinatorial classes that is the categories of sets that can be enumerated, counted...

Generating the category


Cat::CombinatorialClass()

Categories

Cat::BaseCategory

Details

Basic Entries

type

The MuPAD type of the object belonging to the class. Note that if cl is a combinatorial class it is sufficient to call testtype(obj, cl) to test the type of a object.

domtype

The MuPAD domain of the object belonging to the class. Since a combinatorial class can be a facade domain, it can be different from "type".

interfaceCombinatorialClass

The standard common interface of a domain that belongs to Cat::CombinatorialClass.

Method isA: test if an object is an element of the class.

Method size: size of an object.

Method count: count the number of objects.

Method list: list of the objects

Method generator: generator for the objects

Method first: first objects

Method last: last object

Method Next: next object

Method previous: previous object

Method rank: rank object

Method unrank: unrank object

Method random: random object

Method _less: comparison of two objects

Method generatingSeries: the generating series of the class.

Details

Method countFromGenerator: count the number of objects using generation.

Method listFromGenerator: list the number of objects using generation.

Details

Method generatorFromNext: generator for the objects using "first" and "Next"

Method generatorFromPrevious: generator for the objects using "last" and "previous"

Method generatorFromUnrank: generator for the objects using "unrank"

Method generatorFromList: generator for the objects using "list"

Example 1

Suppose that you want to define the combinatorial class of the binary vectors. The size is the length of the vector. It is easy to write a "Next" function, by thinking that a vector is a binary expansion of a number. This is done by searching the first 0 and replacing the initial sequence 11...10 by 00...01. Here is a way to do this:

>> nextBinExp := proc(lst)
           local pos;
       begin
          if (pos := contains(lst, 0)) <> 0 then 
              [ 0$(pos-1), 1, op(lst, pos+1..nops(lst))]
          else FAIL
          end_if;  
       end:
       nextBinExp([1, 1, 0, 1, 0, 1, 1, 0]);
     
                         [0, 0, 1, 1, 0, 1, 1, 0]
        

Here is the way to use that to build a combinatorial class. We have to define "isA" for the type checking and "first", "Next" for generation :

>> domain zeroOneVectors 
       inherits Dom::BaseDomain;
       category Cat::CombinatorialClass;
       axiom    Ax::systemRep;
       
       isA := // Type checking.
       proc(obj         : Type::AnyType,
           size = FAIL : Type::Union(Type::NonNegInt, DOM_FAIL)) : DOM_BOOL
       begin
           if domtype(obj) <> DOM_LIST then return(FALSE); end_if;
           if {op(obj)} minus {0,1} <> {} then return(FALSE); end_if;
           if args(0) = 1 then return(TRUE);
           else
               bool(nops(obj) = size);
           end_if;
       end_proc;
   
       size  := proc(v : dom) : Type::NonNegInt begin nops(v); end_proc;
                   
       first := proc(size : Type::NonNegInt) : dom
                begin
                    [ 0 $ size ];
                end_proc;
   
       Next := proc(lst : dom) : Type::Union(DOM_FAIL, dom)
                   local pos;
               begin
                   if (pos := contains(lst, 0)) <> 0 then 
                       [ 0$(pos-1), 1, op(lst, pos+1..nops(lst))]
                   else FAIL
                   end_if;  
               end_proc;
   end_domain:
     

The type Checking is working:

>> testtype([1, 0, 1], zeroOneVectors);
   testtype([1, 0, 2], zeroOneVectors)
     
                                   TRUE
      
                                   FALSE
        

The method "list" and is provided by Cat::CombinatorialClass

>> zeroOneVectors::list(3)
     
      [[0, 0, 0], [1, 0, 0], [0, 1, 0], [1, 1, 0], [0, 0, 1],
      
         [1, 0, 1], [0, 1, 1], [1, 1, 1]]
        

Together with the method "generator":

>> (g := zeroOneVectors::generator(2); 
   g(), g(), g(), g(), g())
     
                   [0, 0], [1, 0], [0, 1], [1, 1], FAIL
        

The following useful shortcut is also defined

>> zeroOneVectors(3)
     
      [[0, 0, 0], [1, 0, 0], [0, 1, 0], [1, 1, 0], [0, 0, 1],
      
         [1, 0, 1], [0, 1, 1], [1, 1, 1]]
        

A default implementation is provided for the "count" method:

>> zeroOneVectors::count(4)
     
                                    16
        

However, it is very slow, since it simply generates all the elements, and count them:

>> zeroOneVectors::count(10);
   time(zeroOneVectors::count(10))
     
                                   1024
      
                                   240
        

Whenever possible, it is better to implement the "count" method:

>> zeroOneVectors::count := i -> 2^i:
   zeroOneVectors::count(10);
   time(zeroOneVectors::count(10))
     
                                   1024
      
                                     0
        

Changes

[Previous] [Next] [Contents]


MuPAD Combinat, an open source algebraic combinatorics package