Integer compositions¶
A composition \(c\) of a nonnegative integer \(n\) is a list of positive integers (the parts of the composition) with total sum \(n\).
This module provides tools for manipulating compositions and enumerated sets of compositions.
EXAMPLES:
sage: Composition([5, 3, 1, 3])
[5, 3, 1, 3]
sage: list(Compositions(4))
[[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 3], [2, 1, 1], [2, 2], [3, 1], [4]]
AUTHORS:
- Mike Hansen, Nicolas M. Thiery
- MuPAD-Combinat developers (algorithms and design inspiration)
- Travis Scrimshaw (2013-02-03): Removed
CombinatorialClass
-
sage.combinat.composition.
Composition
¶ Integer compositions
A composition of a nonnegative integer \(n\) is a list \((i_1, \ldots, i_k)\) of positive integers with total sum \(n\).
EXAMPLES:
The simplest way to create a composition is by specifying its entries as a list, tuple (or other iterable):
sage: Composition([3,1,2]) [3, 1, 2] sage: Composition((3,1,2)) [3, 1, 2] sage: Composition(i for i in range(2,5)) [2, 3, 4]
You can also create a composition from its code. The code of a composition \((i_1, i_2, \ldots, i_k)\) of \(n\) is a list of length \(n\) that consists of a \(1\) followed by \(i_1-1\) zeros, then a \(1\) followed by \(i_2-1\) zeros, and so on.
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]
You can also create the composition of \(n\) corresponding to a subset of \(\{1, 2, \ldots, n-1\}\) under the bijection that maps the composition \((i_1, i_2, \ldots, i_k)\) of \(n\) to the subset \(\{i_1, i_1 + i_2, i_1 + i_2 + i_3, \ldots, i_1 + \cdots + i_{k-1}\}\) (see
to_subset()
):sage: Composition(from_subset=({1, 2, 4}, 5)) [1, 1, 2, 1] sage: Composition([1, 1, 2, 1]).to_subset() {1, 2, 4}
The following notation equivalently specifies the composition from the set \(\{i_1 - 1, i_1 + i_2 - 1, i_1 + i_2 + i_3 - 1, \dots, i_1 + \cdots + i_{k-1} - 1, n-1\}\) or \(\{i_1 - 1, i_1 + i_2 - 1, i_1 + i_2 + i_3 - 1, \dots, i_1 + \cdots + i_{k-1} - 1\}\) and \(n\). This provides compatibility with Python’s \(0\)-indexing.
sage: Composition(descents=[1,0,4,8,11]) [1, 1, 3, 4, 3] sage: Composition(descents=[0,1,3,4]) [1, 1, 2, 1] sage: Composition(descents=([0,1,3],5)) [1, 1, 2, 1] sage: Composition(descents=({0,1,3},5)) [1, 1, 2, 1]
EXAMPLES:
sage: C = Composition([3,1,2]) sage: TestSuite(C).run()
-
sage.combinat.composition.
Compositions
¶ Set of integer compositions.
A composition \(c\) of a nonnegative integer \(n\) is a list of positive integers with total sum \(n\).
See also
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]
If \(n\) is not specified, this 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: list(Compositions(3)) [[1, 1, 1], [1, 2], [2, 1], [3]] sage: Compositions(3).cardinality() 4
The following examples show 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]) True sage: [4,2] in Compositions(6, inner=[2,3]) False sage: [4,1] in Compositions(5, inner=[2,1], max_slope = 0) True
An example with incompatible constraints:
sage: [4,2] in Compositions(6, inner=[2,2], min_part=3) False
The options
length
,min_length
, andmax_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() [[3, 1], [2, 2], [1, 3]] sage: Compositions(4, min_length=2).list() [[3, 1], [2, 2], [2, 1, 1], [1, 3], [1, 2, 1], [1, 1, 2], [1, 1, 1, 1]] sage: Compositions(4, max_length=2).list() [[4], [3, 1], [2, 2], [1, 3]]
Setting both
min_length
andmax_length
to the same value is equivalent to settinglength
to this value:sage: Compositions(4, min_length=2, max_length=2).list() [[3, 1], [2, 2], [1, 3]]
The options
inner
andouter
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: list(Compositions(4, outer=[3,1,2])) [[3, 1], [2, 1, 1], [1, 1, 2]]
outer
setsmax_length
to the length of its argument. Moreover, the parts ofouter
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, 3], [1, 2, 1]]
This is the list of compositions of 4 bounded below by
[1,1,1]
:sage: Compositions(4, inner=[1,1,1]).list() [[2, 1, 1], [1, 2, 1], [1, 1, 2], [1, 1, 1, 1]]
The options
min_slope
andmax_slope
can be used to set constraints on the slope, that is the differencep[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() [[4], [2, 2], [1, 3], [1, 1, 2], [1, 1, 1, 1]]
Here are the weakly decreasing ones:
sage: Compositions(4, max_slope=0).list() [[4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]]
The following is the list of compositions of 4 such that two consecutive parts differ by at most one:
sage: Compositions(4, min_slope=-1, max_slope=1).list() [[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 consecutive parts is between -2 and 1:
sage: Compositions(5, max_slope=1, min_slope=-2, min_length=2, max_length=4).list() [[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]]
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() [[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.
Note that if you specify
min_part=0
, then the objects produced may have parts equal to zero. This violates the internal assumptions that the composition class makes. Use at your own risk, or preferably consider usingIntegerVectors
instead:sage: Compositions(2, length=3, min_part=0).list() doctest:...: RuntimeWarning: Currently, setting min_part=0 produces Composition objects which violate internal assumptions. Calling methods on these objects may produce errors or WRONG results! [[2, 0, 0], [1, 1, 0], [1, 0, 1], [0, 2, 0], [0, 1, 1], [0, 0, 2]] sage: list(IntegerVectors(2, 3)) [[2, 0, 0], [1, 1, 0], [1, 0, 1], [0, 2, 0], [0, 1, 1], [0, 0, 2]]
The generation algorithm is constant amortized time, and handled by the generic tool
IntegerListsLex
.
-
sage.combinat.composition.
Compositions_all
¶ Class of all compositions.
-
class
sage.combinat.composition.
Compositions_constraints
(*args, **kwds)¶
-
sage.combinat.composition.
Compositions_n
¶ Class of compositions of a fixed \(n\).
-
sage.combinat.composition.
composition_iterator_fast
(n)¶ Iterator over compositions of
n
yielded as lists.