A composition c of a nonnegative integer n is a list of positive integers with total sum n.
EXAMPLES: There are 8 compositions of 4.
sage: Compositions(4).cardinality()
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 equivalent 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 constraints. 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 difference 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.
AUTHORS:
Returns a composition object.
EXAMPLES: 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]
Returns the complement of the composition co. The complement is the reverse of co’s conjugate composition.
EXAMPLES:
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]
Returns the conjugate of the composition comp.
Algorithm from mupad-combinat.
EXAMPLES:
sage: Composition([1, 1, 3, 1, 2, 1, 3]).conjugate()
[1, 1, 3, 3, 1, 3]
Returns the list of descents of the composition co.
EXAMPLES:
sage: Composition([1, 1, 3, 1, 2, 1, 3]).descents()
[0, 1, 4, 5, 7, 8, 11]
Returns True if the composition self is finer than the composition co2; otherwise, it returns False.
EXAMPLES:
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
Returns the major index of the composition co. The major index is defined as the sum of the descents.
EXAMPLES:
sage: Composition([1, 1, 3, 1, 2, 1, 3]).major_index()
31
Returns a list of the peaks of the composition self. The peaks of a composition are the descents which do not immediately follow another descent.
EXAMPLES:
sage: Composition([1, 1, 3, 1, 2, 1, 3]).peaks()
[4, 7]
Returns the refinement composition of self and co2.
EXAMPLES:
sage: Composition([1,2,2,1,1,2]).refinement([5,1,3])
[3, 1, 2]
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.
EXAMPLES:
sage: Composition([4,1,2,3,5]).to_code()
[1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0]
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.
EXAMPLES:
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]]
Returns the combinatorial class of compositions.
EXAMPLES: If n is not specified, 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).cardinality()
4
In addition, the following constraints 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]]
TESTS:
sage: [2,1,3] in Compositions()
True
sage: [] in Compositions()
True
sage: [-2,-1] in Compositions()
False
sage: [0,0] in Compositions()
True
TESTS:
sage: C = Compositions()
sage: C == loads(dumps(C))
True
TESTS:
sage: repr(Compositions())
'Compositions of non-negative integers'
Needed by InfiniteAbstractCombinatorialClass to build __iter__.
TESTS:
sage: Compositions()._infinite_cclass_slice(4) == Compositions(4)
True
sage: it = iter(Compositions()) # indirect doctest
sage: [it.next() for i in range(10)]
[[], [1], [1, 1], [2], [1, 1, 1], [1, 2], [2, 1], [3], [1, 1, 1, 1], [1, 1, 2]]
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
sage: C = Compositions(4, length=2)
sage: C == loads(dumps(C))
True
TESTS:
sage: repr(Compositions(6, min_part=2, length=3))
'Compositions of 6 with constraints length=3, min_part=2'
EXAMPLES:
sage: Compositions(4, length=2).cardinality()
3
sage: Compositions(4, min_length=2).cardinality()
7
sage: Compositions(4, max_length=2).cardinality()
4
sage: Compositions(4, max_part=2).cardinality()
5
sage: Compositions(4, min_part=2).cardinality()
2
sage: Compositions(4, outer=[3,1,2]).cardinality()
3
Returns a list of all the compositions of n.
EXAMPLES:
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]]
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
TESTS:
sage: C = Compositions(3)
sage: C == loads(dumps(C))
True
TESTS:
sage: repr(Compositions(3))
'Compositions of 3'
TESTS:
sage: Compositions(3).cardinality()
4
sage: Compositions(0).cardinality()
1
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()
[[]]
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.
EXAMPLES:
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]
Returns a composition from the list of descents.
EXAMPLES:
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]