[Previous] [Contents]

combinat::words -- words

Introduction

The library combinat::words provides functions for counting, generating, and manipulating words.

Details

Categories

Cat::CombinatorialClass

Entries

domtype

The MuPAD domain used to represent words: DOM_LIST

Method isA: check if an object is a word

Method list: list of the words

Method generator: generator for words

Method alphabetToOrder: ordering function of an alphabet

Method standard: standard permutation of a word

Method evaluation: [ImplState=stable,TestState=stable,DocState=alpha]

Method evaluationPartition: [ImplState=stable,TestState=beta,DocState=alpha]

Method evaluationTable: [ImplState=stable,TestState=stable,DocState=alpha]

Method fromStandardAndEvaluation: [ImplState=stable,TestState=stable,DocState=alpha]

Method shuffle: shuffle product of two words

Method shuffle::generator: generator for the shuffle product of two words

Method shuffleAugmented: augmented shuffle product of two words

Method lexLess: [ImplState=beta,TestState=beta,DocState=beta] strict lexicographic comparison of words

Method degLexLess: [ImplState=beta,TestState=beta,DocState=beta] strict degree lexicographic comparison of words

Method invLexLess: [ImplState=beta,TestState=alpha,DocState=beta] strict inverse lexicographic comparison of words

Method degInvLexLess: [ImplState=beta,TestState=beta,DocState=beta] strict degree inverse lexicographic comparison of words

Method revLexLess: [ImplState=beta,TestState=alpha,DocState=beta] strict reverse lexicographic comparison of words

Method degRevLexLess: [ImplState=beta,TestState=alpha,DocState=beta] strict degree reverse lexicographic comparison of words

Example 1

There are 8 words of length 3 on the alphabet {a,b}:

>> combinat::words::count([a,b],3)
     
                                     8
        

Here is the list:

>> combinat::words::list([a,b],3)
     
      [[a, a, a], [a, a, b], [a, b, a], [a, b, b], [b, a, a],
      
         [b, a, b], [b, b, a], [b, b, b]]
        

For the alphabet of [1,2], it is shorter to write:

>> combinat::words::count(2,3);
   combinat::words::list(2,3);
     
                                     8
      
      [[1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 2, 2], [2, 1, 1],
      
         [2, 1, 2], [2, 2, 1], [2, 2, 2]]
        

When you want to run through the words, you can generate them one by one to save memory:

>> g := combinat::words::generator([a,b],3):
   g();
   g(), g(), g(), g(), g(), g(), g(), g();
   h := combinat::words::generator(2,3):
   h();
   h(), h(), h(), h(), h(), h(), h(), h();
     
                                 [a, a, a]
      
      [a, a, b], [a, b, a], [a, b, b], [b, a, a], [b, a, b],
      
         [b, b, a], [b, b, b], FAIL
      
                                 [1, 1, 1]
      
      [1, 1, 2], [1, 2, 1], [1, 2, 2], [2, 1, 1], [2, 1, 2],
      
         [2, 2, 1], [2, 2, 2], FAIL
        

Typically, this would be used as follows:

>> g := combinat::words::generator(2,2):
   while (p := g()) <> FAIL do print(p): end:
     
                                  [1, 1]
      
                                  [1, 2]
      
                                  [2, 1]
      
                                  [2, 2]
        

Example 2

Most operations on words, such as standardization, depends on an alphabet ordering. You can get the ordering function associated with an alphabet with combinat::words::alphabetToOrder:

>> isSmaller := combinat::words::alphabetToOrder([c,b,a,d]):
   isSmaller(a,b), bool(isSmaller(a,b));
   isSmaller(a,d), bool(isSmaller(a,d));
     
                               3 < 2, FALSE
      
                                3 < 4, TRUE
        

Note that isSmaller does not return a boolean value but rather an expression whose evaluation is boolean.

If the alphabet is given by means of a set, an unspecified fixed order is chosen:

>> isSmaller := combinat::words::alphabetToOrder({c,b,a,d}):
   isSmaller(a,b), bool(isSmaller(a,b));
   isSmaller(a,d), bool(isSmaller(a,d));
     
                                2 < 3, TRUE
      
                               2 < 1, FALSE
        

Example 3

You can compute the standard permutation of a word:

>> combinat::words::standard([1,2,3,2,2,1,2,1])
     
                         [1, 4, 8, 5, 6, 2, 7, 3]
        

The standard permutation of a word and the word itself have by definition the same inversions (see combinat::permutations::inversions):

>> combinat::permutations::inversions([1,2,3,2,2,1,2,1]);
   combinat::permutations::inversions(
      combinat::words::standard([1,2,3,2,2,1,2,1]));
     
      [{2, 6}, {2, 8}, {3, 4}, {3, 5}, {3, 6}, {3, 7}, {3, 8},
      
         {4, 6}, {4, 8}, {5, 6}, {5, 8}, {7, 8}]
      
      [{2, 6}, {2, 8}, {3, 4}, {3, 5}, {3, 6}, {3, 7}, {3, 8},
      
         {4, 6}, {4, 8}, {5, 6}, {5, 8}, {7, 8}]
        

If your word is on an alphabet which cannot be ordered with <, you have to specify the order:

>> combinat::words::standard([a,b,a,c,b,c,a]);
     
      Error: Can't evaluate to boolean [_less];
      during evaluation of 'combinat::words::standard'
        

You can do that by specifying explicitly the alphabet:

>> combinat::words::standard([a,b,a,c,b,c,a],[a,b,c,d]);
     
                           [1, 4, 2, 6, 5, 7, 3]
        

Another way is to provide an ordering function:

>> isSmaller := (x,y) -> (expr2text(x) < expr2text(y)):
   combinat::words::standard([a,b,a,c,b,c,a],isSmaller);
     
                           [1, 4, 2, 6, 5, 7, 3]
        

Example 4

You can compute the shuffle product of two words:

>> combinat::words::shuffle([1,2,3],[a,b]);
     
      [[1, 2, 3, a, b], [1, 2, a, 3, b], [1, 2, a, b, 3],
      
         [1, a, 2, 3, b], [1, a, 2, b, 3], [1, a, b, 2, 3],
      
         [a, 1, 2, 3, b], [a, 1, 2, b, 3], [a, 1, b, 2, 3],
      
         [a, b, 1, 2, 3]]
        
You can also obtain them through a generator:
>> g:=combinat::words::shuffle::generator([1,2,3],[a,b]):
   g(); g();
   g() $ i=1..9;
     
                              [1, 2, 3, a, b]
      
                              [1, 2, a, 3, b]
      
      [1, 2, a, b, 3], [1, a, 2, 3, b], [1, a, 2, b, 3],
      
         [1, a, b, 2, 3], [a, 1, 2, 3, b], [a, 1, 2, b, 3],
      
         [a, 1, b, 2, 3], [a, b, 1, 2, 3], FAIL
        

Finally, here is the list of the words in the augmented shuffle product of [1,2] and [a,b]:

>> combinat::words::shuffleAugmented([1, 2], [a, b])
     
      [[a, b, 1, 2], [a, 1, b, 2], [1, a, b, 2], [a + 1, b, 2],
      
         [a, b + 1, 2], [a, 1, 2, b], [1, a, 2, b], [a + 1, 2, b],
      
         [1, 2, a, b], [1, a + 2, b], [a, 1, b + 2], [1, a, b + 2],
      
         [a + 1, b + 2]]
        

Super-Domain

Dom::BaseDomain

Axioms

Ax::systemRep

[Previous] [Contents]


MuPAD Combinat, an open source algebraic combinatorics package