combinat::subwords
--
subwords of a word
The library combinat::subwords
provides functions for
counting, generating, and manipulating the subwords of a word.
combinat::words
). A subword is generated as many times
as it appears in the word.Cat::CombinatorialClass
The MuPAD domain used to represent subwords:
DOM_LIST
.
count(word A)
count(word A, nonnegative integer k <, Repeat>)
list(word A)
list(word A, nonnegative integer k <, Repeat>)
generator(word A)
generator(word A, nonnegative integer k <, Repeat>)
first(word A)
first(word A, nonnegative integer k <, Repeat>)
last(word A)
last(word A, nonnegative integer k <, Repeat>)
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]
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
Ax::systemRep
MuPAD Combinat, an open source algebraic combinatorics package