combinat::compositions
--
compositions of an integer
The library combinat::compositions
provides functions for counting,
generating, and manipulating compositions.
c
of a nonnegative integer n
is a list of positive integers with total sum n
.Cat::IntegerListsLexClass
combinat::partitions
, combinat::words
The MuPAD domain of compositions: DOM_LIST
isA(any type co <, nonnegative integer n <, constraints>>)
co
is a composition.n
is present, returns whether co
is a
composition of n
.co
is a composition
satisfying constraints
.
count(nonnegative integer n <, constraints>)
n
satisfying
constraints
.
generator(nonnegative integer n <, constraints>)
n
satisfying
constraints
.
list(nonnegative integer n <, constraints>)
n
satisfying
constraints
.
first(nonnegative integer n <, constraints>)
n
satisfying
constraints
or FAIL
if there is none.
Next(composition c <, constraints>)
c
satisfying
constraints
or FAIL
if there is none.
descents(composition c)
c
descentsSet(composition c)
c
fromDescents(descent set s)
fromDescents(descent list l)
c
whose descents set is s
or l
majorIndex(composition c)
c
, defined as the sum of the
descents.
isFiner(composition c1, composition c2)
c1
is finer than the composition
c2
.
finer(composition c)
c
. Note that
compositons::finer
is a full combinatorial class that
implement the standard methods compositions::finer::count
and
compositions::finer::generators
.
fatter(composition c)
c
. Note
that compositons::fatter
is a combinatorial class that
implement the standard methods compositions::fatter::count
and
compositions::fatter::generators
.
This example shows how to test if an object is of type
combinat::compositions
:
>> combinat::compositions::isA([3,4]);
combinat::compositions::isA([3,4],7);
combinat::compositions::isA([3,4],5);
TRUE TRUE FALSE
The combinat::compositions::isA
function admets
the same constraints than other functions in the package.
>> combinat::compositions::isA([4,2], 6, Inner=[2, 2], MinPart=2);
combinat::compositions::isA([4,2], 6, Inner=[2, 2], MaxPart=4);
TRUE TRUE
Please note that given constraints should be compatible:
>> combinat::compositions::isA([4,1], 5, Inner=[2, 1], MinPart=2);
TRUE
See further examples for other constraints.
There are 8 compositions of 4:
>> combinat::compositions::count(4)
8
Here is the list:
>> combinat::compositions::list(4)
[[4], [3, 1], [2, 2], [2, 1, 1], [1, 3], [1, 2, 1], [1, 1, 2], [1, 1, 1, 1]]
You can use the function combinat::compositions::first
to get
the ``first'' composition of a number:
>> combinat::compositions::first(4)
[4]
Using combinat::compositions::Next
, you can calculate the
``next'' composition. This function takes as argument the
composition relative to which you want the next one:
>> combinat::compositions::Next([4])
[3, 1]
combinat::compositions::Next
returns FAIL
when the
input is the last composition:
>> combinat::compositions::Next([1, 1, 1, 1])
FAIL
When you want to run through the compositions of a number, you can generate them one by one to save memory:
>> g := combinat::compositions::generator(3):
g(); g(); g(); g(); g();
[3] [2, 1] [1, 2] [1, 1, 1] FAIL
Typically, this would be used as follows:
>> g := combinat::compositions::generator(3):
while (p := g()) <> FAIL do print(p): end:
[3] [2, 1] [1, 2] [1, 1, 1]
The options Length, MinLength, and MaxLength can be used to set length constraints. This is the list of the compositions of 4 of length 2:
>> combinat::compositions::list(4, Length=2)
[[3, 1], [2, 2], [1, 3]]
This is the list of the compositions of 4 of length at least 2:
>> combinat::compositions::list(4, MinLength=2)
[[3, 1], [2, 2], [2, 1, 1], [1, 3], [1, 2, 1], [1, 1, 2], [1, 1, 1, 1]]
This is the list of the compositions of 4 of length at most 2:
>> combinat::compositions::list(4, MaxLength=2)
[[4], [3, 1], [2, 2], [1, 3]]
Setting both MinLength and MaxLength to the same value is equivalent to setting Length to this value. This is again the list of the compositions of 4 of length 2:
>> combinat::compositions::list(4, MinLength=2, MaxLength=2)
[[3, 1], [2, 2], [1, 3]]
The options MinPart and MaxPart can be used to set constraints on the sizes of all parts. Using MaxPart, you can select compositions having only small entries. This is the list of the compositions of 4 with all parts at most 2:
>> combinat::compositions::list(4, MaxPart=2)
[[2, 2], [2, 1, 1], [1, 2, 1], [1, 1, 2], [1, 1, 1, 1]]
MinPart is complementary to MaxPart and selects compositions having only large parts (it takes a non-negative value). This is the list of the compositions of 4 with all parts at least 2:
>> combinat::compositions::list(4, MinPart=2)
[[4], [2, 2]]
By default, the parts of a composition have to be positive. This can be changed using the option MinPart. In the following example, the options Length and MinPart are combined together to obtain the list of the compositions of 4 with 3 nonnegative parts:
>> combinat::compositions::list(4, Length=3, MinPart=0)
[[4, 0, 0], [3, 1, 0], [3, 0, 1], [2, 2, 0], [2, 1, 1], [2, 0, 2], [1, 3, 0], [1, 2, 1], [1, 1, 2], [1, 0, 3], [0, 4, 0], [0, 3, 1], [0, 2, 2], [0, 1, 3], [0, 0, 4]]
If the list you ask for is infinite, the program will not finish,
as it is be the case for combinat::compositions::list(4,
MinPart=0);
Two compositions are considered equivalent whenever they differ only by trailing zeroes. Whenever two equivalent compositions satisfy the constraints, only the shortest one is considered. Hence, this is the list of compositions of 4 with 2 or 3 nonnegative parts:
>> combinat::compositions::list(4, MinLength=2, MaxLength=3, MinPart=0)
[[4, 0], [3, 1], [3, 0, 1], [2, 2], [2, 1, 1], [2, 0, 2], [1, 3], [1, 2, 1], [1, 1, 2], [1, 0, 3], [0, 4], [0, 3, 1], [0, 2, 2], [0, 1, 3], [0, 0, 4]]
The options Inner, and Outer can be used to set part-by-part
containment constraints. This is the list of the compositions of 4
bounded above by [3, 1, 2]
:
>> combinat::compositions::list(4, Outer=[3, 1, 2])
[[3, 1], [2, 1, 1], [1, 1, 2]]
Outer sets MaxLength to the length of its argument. Moreover, the parts of Outer may be infinite to clear the constraint on specific parts. This is the list of compositions of 4 of length at most 3 such that the first and third parts are at most 1:
>> combinat::compositions::list(4, Outer=[1, infinity, 1])
[[1, 3], [1, 2, 1]]
This is the list of compositions of 4 bounded below by
[1, 1, 1]
:
>> combinat::compositions::list(4, Inner=[1, 1, 1])
[[2, 1, 1], [1, 2, 1], [1, 1, 2], [1, 1, 1, 1]]
The options MinSlope and MaxSlope can be used to set
constraints on the slope, that is on the difference
p[i+1]-p[i]
of two consecutive parts. This is the list of
the increasing compositions of 4:
>> combinat::compositions::list(4, MinSlope=0)
[[4], [2, 2], [1, 3], [1, 1, 2], [1, 1, 1, 1]]
This is the list of compositions of 4 such that two consecutive parts differ by at most one unit:
>> combinat::compositions::list(4, MinSlope=-1, MaxSlope=1)
[[4], [2, 2], [2, 1, 1], [1, 2, 1], [1, 1, 2], [1, 1, 1, 1]]
The constraints can be combined together in all reasonable ways. This is the list of compositions of 5 of length between 2 and 4 such that the difference between two consecutive parts is between -2 and 1:
>> combinat::compositions::list(5,
MaxSlope=1, MinSlope=-2,
MinLength=2, MaxLength=4)
[[3, 2], [3, 1, 1], [2, 3], [2, 2, 1], [2, 1, 2], [2, 1, 1, 1], [1, 2, 2], [1, 2, 1, 1], [1, 1, 2, 1], [1, 1, 1, 2]]
Idem with an Outer constraint:
>> combinat::compositions::list(5,
MaxSlope=1, MinSlope=-2,
MinLength=2, MaxLength=4,
Outer=[2,5,2])
[[2, 3], [2, 2, 1], [2, 1, 2], [1, 2, 2]]
However, providing incoherent constraints may yield strange results. It is up to the user to ensure that the Inner and Outer compositions themselves satisfy the parts and slope constraints:
>> combinat::compositions::list(5, Inner=[2, 1], MinPart=2)
[[4, 1], [3, 2], [2, 3], [2, 1, 2]]
One can check that those two compositions are not comparable for the refinement order:
>> combinat::compositions::isFiner([4,1,2],[3,1,3]);
combinat::compositions::isFiner([3,1,3],[4,1,2]);
FALSE FALSE
To get the list of compositions finer than [4,1,2]
,
you can use:
>> combinat::compositions::finer([4,1,2]);
[[4, 1, 2], [4, 1, 1, 1], [3, 1, 1, 2], [3, 1, 1, 1, 1], [2, 2, 1, 2], [2, 2, 1, 1, 1], [2, 1, 1, 1, 2], [2, 1, 1, 1, 1, 1], [1, 3, 1, 2], [1, 3, 1, 1, 1], [1, 2, 1, 1, 2], [1, 2, 1, 1, 1, 1], [1, 1, 2, 1, 2], [1, 1, 2, 1, 1, 1], [1, 1, 1, 1, 1, 2], [1, 1, 1, 1, 1, 1, 1]]
To get the list of compositions fatter than
[4,1,2]
, you can use:
>> combinat::compositions::fatter([4,1,2]);
[[7], [5, 2], [4, 3], [4, 1, 2]]
If you only want their number, you can ask:
>> combinat::compositions::fatter::count([4,1,2]);
4
Cat::IntegerListsLexClass
with, by default,
MinPart=1
. The complexity of the generation algorithm is
constant time amortized for each composition generated.Except for the trivial cases, counting is done by brute force generation.
Ax::systemRep
MuPAD Combinat, an open source algebraic combinatorics package