Module: sage.combinat.composition
Compositions
A composition c of a nonnegative integer n is a list of positive integers with total sum n.
There are 8 compositions of 4.
sage: Compositions(4).count() 8
Here is the list of them:
sage: Compositions(4).list() [[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 3], [2, 1, 1], [2, 2], [3, 1], [4]]
You can use the .first() method to get the 'first' composition of a number.
sage: Compositions(4).first() [1, 1, 1, 1]
You can also calculate the 'next' composition given the current one.
sage: Compositions(4).next([1,1,2]) [1, 2, 1]
The following examples shows how to test whether or not an object is a composition.
sage: [3,4] in Compositions() True sage: [3,4] in Compositions(7) True sage: [3,4] in Compositions(5) False
Similarly, one can check whether or not an object is a composition which satisfies further constraints.
sage: [4,2] in Compositions(6, inner=[2,2], min_part=2) True sage: [4,2] in Compositions(6, inner=[2,2], min_part=2) True sage: [4,2] in Compositions(6, inner=[2,2], min_part=3) False
Note that the given constraints should compatible.
sage: [4,1] in Compositions(5, inner=[2,1], min_part=1) True
The options length, min_length, and max_length can be used to set length constraints on the compositions. For example, the compositions of 4 of length equal to, at least, and at most 2 are given by:
sage: Compositions(4, length=2).list() [[1, 3], [2, 2], [3, 1]] sage: Compositions(4, min_length=2).list() [[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 3], [2, 1, 1], [2, 2], [3, 1]] sage: Compositions(4, max_length=2).list() [[1, 3], [2, 2], [3, 1], [4]]
Setting both min_length and max_length to the same value is equaivalent to setting length to this value.
sage: Compositions(4, min_length=2, max_length=2).list() [[1, 3], [2, 2], [3, 1]]
The options inner and outer can be used to set part-by-part containment constaints. The list of compositions of 4 bounded above by [3,1,2] is given by:
sage: Compositions(4, outer=[3,1,2]).list() [[1, 1, 2], [2, 1, 1], [3, 1]]
Outer sets max_length 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:
sage: Compositions(4, outer=[1,oo,1]).list() [[1, 2, 1], [1, 3]]
This is the list of compositions of 4 bounded below by [1,1,1].
sage: Compositions(4, inner=[1,1,1]).list() [[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [2, 1, 1]]
The options min_slope and max_slope can be used to set constraints on the slope, that is the difference p[i+1]-p[i] of two consecutive parts. The following is the list of weakly increasing compositions of 4.
sage: Compositions(4, min_slope=0).list() [[1, 1, 1, 1], [1, 1, 2], [1, 3], [2, 2], [4]]
The following is the list of compositions of 4 such that two consecutive parts differ by at most one unit:
sage: Compositions(4, min_slope=-1, max_slope=1).list() [[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 2], [4]]
The constraints can be combinat together in all reasonable ways. This is the list of compositions of 5 of length between 2 and 4 such that the differnce between consecutive parts is between -2 and 1.
sage: Compositions(5, max_slope=1, min_slope=-2, min_length=2, max_length=4).list() [[1, 1, 1, 2], [1, 1, 2, 1], [1, 2, 1, 1], [1, 2, 2], [2, 1, 1, 1], [2, 1, 2], [2, 2, 1], [2, 3], [3, 1, 1], [3, 2]]
We can do the same thing with an outer constraint:
sage: Compositions(5, max_slope=1, min_slope=-2, min_length=2, max_length=4, outer=[2,5,2]).list() [[1, 2, 2], [2, 1, 2], [2, 2, 1], [2, 3]]
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.
Author: -Mike Hansen -MuPAD-Combinat developers (for algorithms and design inspiration)
Module-level Functions
[co=None], [descents=None], [code=None]) |
Returns a composition object.
The standard way to create a composition is by specifying it as a list.
sage: Composition([3,1,2]) [3, 1, 2]
You can create a composition from a list of its descents.
sage: Composition([1, 1, 3, 4, 3]).descents() [0, 1, 4, 8, 11] sage: Composition(descents=[1,0,4,8,11]) [1, 1, 3, 4, 3]
You can also create a composition from its code.
sage: Composition([4,1,2,3,5]).to_code() [1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0] sage: Composition(code=_) [4, 1, 2, 3, 5] sage: Composition([3,1,2,3,5]).to_code() [1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0] sage: Composition(code=_) [3, 1, 2, 3, 5]
[n=None]) |
Returns the combinatorial class of compositions.
If n is not specificied, it returns the combinatorial class of all (non-negative) integer compositions.
sage: Compositions() Compositions of non-negative integers sage: [] in Compositions() True sage: [2,3,1] in Compositions() True sage: [-2,3,1] in Compositions() False
If n is specified, it returns the class of compositions of n.
sage: Compositions(3) Compositions of 3 sage: Compositions(3).list() [[1, 1, 1], [1, 2], [2, 1], [3]] sage: Compositions(3).count() 4
In addition, the following constaints can be put on the compositions: length, min_part, max_part, min_length, max_length, min_slope, max_slope, inner, and outer. For example,
sage: Compositions(3, length=2).list() [[1, 2], [2, 1]] sage: Compositions(4, max_slope=0).list() [[1, 1, 1, 1], [2, 1, 1], [2, 2], [3, 1], [4]]
code) |
Return the composition from its code.The code of a composition is a list of length self.size() of 1s and 0s such that there is a 1 wherever a new part starts.
sage: import sage.combinat.composition as composition sage: Composition([4,1,2,3,5]).to_code() [1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0] sage: composition.from_code(_) [4, 1, 2, 3, 5] sage: Composition([3,1,2,3,5]).to_code() [1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0] sage: composition.from_code(_) [3, 1, 2, 3, 5]
descents, [nps=None]) |
Returns a composition from the list of descents.
sage: Composition([1, 1, 3, 4, 3]).descents() [0, 1, 4, 8, 11] sage: sage.combinat.composition.from_descents([1,0,4,8],12) [1, 1, 3, 4, 3] sage: sage.combinat.composition.from_descents([1,0,4,8,11]) [1, 1, 3, 4, 3]
Class: Composition_class
Functions: complement,
conjugate,
descents,
is_finer,
major_index,
peaks,
refinement,
to_code,
to_skew_partition
self) |
Returns the complement of the composition co. The complement is the reverse of co's conjugate composition.
sage: Composition([1, 1, 3, 1, 2, 1, 3]).conjugate() [1, 1, 3, 3, 1, 3] sage: Composition([1, 1, 3, 1, 2, 1, 3]).complement() [3, 1, 3, 3, 1, 1]
self) |
Returns the conjugate of the composition comp.
Algorithm from mupad-combinat.
sage: Composition([1, 1, 3, 1, 2, 1, 3]).conjugate() [1, 1, 3, 3, 1, 3]
self, [final_descent=False]) |
Returns the list of descents of the composition co.
sage: Composition([1, 1, 3, 1, 2, 1, 3]).descents() [0, 1, 4, 5, 7, 8, 11]
self, co2) |
Returns True if the composition self is finer than the composition co2; otherwise, it returns False.
sage: Composition([4,1,2]).is_finer([3,1,3]) False sage: Composition([3,1,3]).is_finer([4,1,2]) False sage: Composition([1,2,2,1,1,2]).is_finer([5,1,3]) True sage: Composition([2,2,2]).is_finer([4,2]) True
self) |
Returns the major index of the composition co. The major index is defined as the sum of the descents.
sage: Composition([1, 1, 3, 1, 2, 1, 3]).major_index() 31
self) |
Returns a list of the peaks of the composition self.
The peaks are the positions i in the compositions such that self[i-1] < self[i] > self[i+1]. Note that len(self)-1 is never a peak.
sage: Composition([1, 1, 3, 1, 2, 1, 3]).peaks() [2, 4]
self, co2) |
Returns the refinement composition of self and co2.
sage: Composition([1,2,2,1,1,2]).refinement([5,1,3]) [3, 1, 2]
self) |
Returns the code of the composition self. The code of a composition is a list of length self.size() of 1s and 0s such that there is a 1 wherever a new part starts.
sage: Composition([4,1,2,3,5]).to_code() [1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0]
self, [overlap=1]) |
Returns the skew partition obtained from the composition co. The parameter overlap indicates the number of boxes that are covered by boxes of the previous line.
sage: Composition([3,4,1]).to_skew_partition() [[6, 6, 3], [5, 2]] sage: Composition([3,4,1]).to_skew_partition(overlap=0) [[8, 7, 3], [7, 3]]
Class: Compositions_all
self) |
TESTS:
sage: C = Compositions() sage: C == loads(dumps(C)) True
Functions: list
self) |
TESTS:
sage: Compositions().list() Traceback (most recent call last): ... NotImplementedError
Special Functions: __contains__,
__init__,
__repr__
self, x) |
TESTS:
sage: [2,1,3] in Compositions() True sage: [] in Compositions() True sage: [-2,-1] in Compositions() False sage: [0,0] in Compositions() True
self) |
TESTS:
sage: repr(Compositions()) 'Compositions of non-negative integers'
Class: Compositions_constraints
self, n) |
sage: C = Compositions(4, length=2) sage: C == loads(dumps(C)) True
Functions: count,
list
self) |
sage: Compositions(4, length=2).count() 3 sage: Compositions(4, min_length=2).count() 7 sage: Compositions(4, max_length=2).count() 4 sage: Compositions(4, max_part=2).count() 5 sage: Compositions(4, min_part=2).count() 2 sage: Compositions(4, outer=[3,1,2]).count() 3
self) |
Returns a list of all the compositions of n.
sage: Compositions(4, length=2).list() [[1, 3], [2, 2], [3, 1]] sage: Compositions(4, min_length=2).list() [[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 3], [2, 1, 1], [2, 2], [3, 1]] sage: Compositions(4, max_length=2).list() [[1, 3], [2, 2], [3, 1], [4]] sage: Compositions(4, max_part=2).list() [[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 2]] sage: Compositions(4, min_part=2).list() [[2, 2], [4]] sage: Compositions(4, outer=[3,1,2]).list() [[1, 1, 2], [2, 1, 1], [3, 1]] sage: Compositions(4, outer=[1,'inf',1]).list() [[1, 2, 1], [1, 3]] sage: Compositions(4, inner=[1,1,1]).list() [[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [2, 1, 1]] sage: Compositions(4, min_slope=0).list() [[1, 1, 1, 1], [1, 1, 2], [1, 3], [2, 2], [4]] sage: Compositions(4, min_slope=-1, max_slope=1).list() [[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 2], [4]] sage: Compositions(5, max_slope=1, min_slope=-2, min_length=2, max_length=4).list() [[1, 1, 1, 2], [1, 1, 2, 1], [1, 2, 1, 1], [1, 2, 2], [2, 1, 1, 1], [2, 1, 2], [2, 2, 1], [2, 3], [3, 1, 1], [3, 2]] sage: Compositions(5, max_slope=1, min_slope=-2, min_length=2, max_length=4, outer=[2,5,2]).list() [[1, 2, 2], [2, 1, 2], [2, 2, 1], [2, 3]]
Special Functions: __contains__,
__init__,
__repr__
self, x) |
TESTS:
sage: [2, 1] in Compositions(3, length=2) True sage: [2,1,2] in Compositions(5, min_part=1) True sage: [2,1,2] in Compositions(5, min_part=2) False
self) |
TESTS:
sage: repr(Compositions(6, min_part=2, length=3)) 'Compositions of 6 with constraints length=3, min_part=2'
Class: Compositions_n
self, n) |
TESTS:
sage: C = Compositions(3) sage: C == loads(dumps(C)) True
Functions: count,
list
self) |
TESTS:
sage: Compositions(3).count() 4 sage: Compositions(0).count() 1
self) |
TESTS:
sage: Compositions(4).list() [[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 3], [2, 1, 1], [2, 2], [3, 1], [4]] sage: Compositions(0).list() [[]]
Special Functions: __contains__,
__init__,
__repr__
self, x) |
TESTS:
sage: [2,1,3] in Compositions(6) True sage: [2,1,2] in Compositions(6) False sage: [] in Compositions(0) True sage: [0] in Compositions(0) True
self) |
TESTS:
sage: repr(Compositions(3)) 'Compositions of 3'