1. Defining new combinatorial classes

For shortening the notations, we export the library combinat:

  export(combinat):

Let us define one of the most trivial combinatorial classes:

domain oddIntegers

    // This is a domain (not a library):

    inherits Dom::BaseDomain;

    // This is a graded combinatorial class:

    category Cat::GradedCombinatorialClass,

             // and a facade domain:

             Cat::FacadeDomain(DOM_INT);

 

     info_str := "The class of non negative odd integers";

 

     isA := n -> bool(testtype(n, Type::PosInt) and n mod 2 = 1);

    // The size of an odd integer is itself

    size  := n -> n;

    count := n -> if n mod 2 = 1 then 1 else 0 end_if;

    list  := n -> if n mod 2 = 1 then [n] else [] end_if;

 

     // No need to define generator;

    // it is defined via list by default

end_domain:

In a first approximation, the three lines inherits, category, and axiom may be safely ignored and kept verbatim. For a deeper understanding, we strongly recommend to read the detailed explanations about the implementation of combinatorial classes in the design notes.

Now, this combinatorial class can be used like all the others:

testtype(x, oddIntegers), testtype(-3, oddIntegers),

testtype(2, oddIntegers), testtype(3, oddIntegers);

math

oddIntegers::count(3);

math

oddIntegers::list(5)

math

In particular, it can be used as building block for constructing new combinatorial classes like, say, integer partitions with odd parts:

oddPartsPartitions := combinat::decomposableObjects

                         ([P = Multiset(oddIntegers)]):

oddPartsPartitions::list(5)

math

Exercise: Improve the definition above so that oddIntegers::count(-1) raises an error instead of returning math.

It is often practical to define a sub-class of an existing class. Here we show how to define the class of the permutations of [1,2,3]:

domain permutationsOf123

    // Inherits all the methods from combinat::permutations

    inherits permutations;

    category Cat::CombinatorialClass,

             Cat::FacadeDomain(combinat::permutations);

 

     info_str := "the class of the permutations of [1,2,3]";

 

     // Redefinition of isA, count and generator

    isA := (p) -> permutations::isA(p, [1,2,3]);

    count     := () -> permutations::count([1,2,3]);

    generator := () -> permutations::generator([1,2,3]);

 

     // No need to redefine list, since it is

    // defined via generator by default

end_domain:

Let us use this new combinatorial class:

testtype(x,            permutationsOf123),

testtype([1, 2, 3, 4], permutationsOf123),

testtype([1, 2, 2],    permutationsOf123),

testtype([1, 3, 2],    permutationsOf123);

math

permutationsOf123::count();

math

permutationsOf123::list()

math

Note: instead of implementing permutationsOf123 by hand, we could have alternatively used the generic utility combinat::subClass; it allows one to automatically define a sub-class of an existing combinatorial class by providing extra parameters to be passed down to all the methods count, list, etc.:

permutationsOf123 := subClass(permutations, Parameters = 3):

permutationsOf123::list()

math

[2]

Exercises:

To conclude, we define the combinatorial class of Fibonacci words. Essentially, we reuse the definition of fiWords above, and wrap it into a domain to add type checking:

domain FibonacciWords

    inherits Dom::BaseDomain;

    // The objects of this class are defined by a grammar

    category Cat::DecomposableClass,

    // The objects this class are represented by lists:

             Cat::FacadeDomain(DOM_LIST);

 

     info_str := "the class of Fibonacci words";

 

     // The type of the elements of this class:

    // a procedure that tests if w is a Fibonacci word

    isA := proc(w : Type::AnyType,

                size = 0 : Type::NonNegInt)

        local i;

        begin

            if domtype(w) <> DOM_LIST then return(FALSE); end_if;

            for i from 1 to nops(w) do

                if (w[i] <> A and w[i] <> B) or

                   (i < nops(w) and w[i]=B and w[i+1]=B) then

                    return(FALSE);

                end_if;

            end_for;

            if args(0) = 1 then TRUE else

                bool(nops(w) = size);

            end_if;

        end_proc;

 

     // The size of a Fibonacci word is its length

    size := nops;

 

     // The grammar which defines the objects of this class

    grammar := decomposableObjects(

        [FiWords    = Alias(FiWordsRec, DOM_LIST),

         FiWordsRec = Union(

             Epsilon(),

             Alias(Prod(Atom(A), FiWordsRec), op),

             Atom(B),

             Alias(Prod(Atom(B), Atom(A), FiWordsRec), op))]);

end_domain:

Now, we can do type checking with this domain:

testtype(x, FibonacciWords),

testtype([A, B, C], FibonacciWords),

testtype([A, B, B], FibonacciWords),

testtype([A, B, A], FibonacciWords)

math

And of course, we can still use all the previous functionalities of fiWords:

FibonacciWords::list(4);

math

 

FibonacciWords::count(4);

math

 

And finally if we wanted to extract the second element of the list without expanding it we can ask for the words of rank 2 in the list:

 

FibonacciWords::unrank(2, 4)

math

 

Exercises: