[Previous] [Next] [Contents]

combinat::subwords -- subwords of a word

Introduction

The library combinat::subwords provides functions for counting, generating, and manipulating the subwords of a word.

Details

Categories

Cat::CombinatorialClass

Related Domains

combinat::words

Entries

domtype

The MuPAD domain used to represent subwords: DOM_LIST.

Method count: number of subwords of a word

Method list: list of the subwords of a word

Method generator: generator for subwords of a word

Method first: first subword of a word

Method last: last subword of a word

Example 1

There are 8 subwords of the word [a, c, b]:

>> combinat::subwords::count([a, c, b])
     
                                     8
        

Here is the list:

>> combinat::subwords::list([a, b, c])
     
          [[], [a], [b], [c], [a, b], [a, c], [b, c], [a, b, c]]
        

To compute the subwords of a given length:

>> combinat::subwords::count([a, c, b, b, c], 3);
   combinat::subwords::list([a, c, b, b, c], 3)
     
                                    10
      
      [[a, c, b], [a, c, b], [a, c, c], [a, b, b], [a, b, c],
      
         [a, b, c], [c, b, b], [c, b, c], [c, b, c], [b, b, c]]
        

Note that the word [a, c, b] is repeated twice.

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

>> g := combinat::subwords::generator([a, c, b, b, c], 3):
   g(), g();
   g(), g(), g(), g(), g(), g(), g(), g(), g();
     
                           [a, c, b], [a, c, b]
       
      [a, c, c], [a, b, b], [a, b, c], [a, b, c], [c, b, b],
      
         [c, b, c], [c, b, c], [b, b, c], FAIL
        

Typically, this would be used as follows:

>> g := combinat::subwords::generator([a, b, b, a], 2):
   while (p := g()) <> FAIL do print(p): end:
     
                                  [a, b]
      
                                  [a, b]
      
                                  [a, a]
      
                                  [b, b]
      
                                  [b, a]
      
                                  [b, a]
        

The ``first'' and ``last'' subwords of length k, also called left and right factors are computed in this example:

>> combinat::subwords::first([a, b, b, a, d, b, a], 3);
   combinat::subwords::last([a, b, b, a, d, b, a], 3);
     
                                 [a, b, b]
       
                                 [d, b, a]
        

Example 2

To list the non-decreasing words of [a, b, d], you just have to list the subwords of [a, b, d] with repetitions:

>> combinat::subwords::list([a, b, d], 3, Repeat);
     
      [[a, a, a], [a, a, b], [a, a, d], [a, b, b], [a, b, d],
      
         [a, d, d], [b, b, b], [b, b, d], [b, d, d], [d, d, d]]
        

It also works for an input word with repeated letters:

>> combinat::subwords::list([a, b, b], 3, Repeat);
     
      [[a, a, a], [a, a, b], [a, a, b], [a, b, b], [a, b, b],
      
         [a, b, b], [b, b, b], [b, b, b], [b, b, b], [b, b, b]]
        

And also with generators:

>> g := combinat::subwords::generator([a, b, b], 3, Repeat):
   g(), g();
   g(), g(), g(), g(), g(), g(), g(), g(), g();
     
                           [a, a, a], [a, a, b]
      
      [a, a, b], [a, b, b], [a, b, b], [a, b, b], [b, b, b],
      
         [b, b, b], [b, b, b], [b, b, b], FAIL
        

Super-Domain

Dom::BaseDomain

Axioms

Ax::systemRep

[Previous] [Next] [Contents]


MuPAD Combinat, an open source algebraic combinatorics package