Integer compositions¶
A composition of a nonnegative integer
is a list of positive integers
(the parts of the composition) with total sum
.
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
-
class
sage.combinat.composition.
Composition
(parent, *args, **kwds)¶ Bases:
sage.combinat.combinat.CombinatorialElement
Integer compositions
A composition of a nonnegative integer
is a list
of positive integers with total sum
.
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
of
is a list of length
that consists of a
followed by
zeros, then a
followed by
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
corresponding to a subset of
under the bijection that maps the composition
of
to the subset
(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
or
and
. This provides compatibility with Python’s
-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()
-
complement
()¶ Return the complement of the composition
self
.The complement of a composition
is defined as follows:
If
is the empty composition, then the complement is the empty composition as well. Otherwise, let
be the descent set of
(that is, the subset
of
, where
is written as
). Then, the complement of
is defined as the composition of size
whose descent set is
.
The complement of a composition
also is the reverse composition (
reversed()
) of the conjugate (conjugate()
) of.
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]
-
conjugate
()¶ Return the conjugate of the composition
self
.The conjugate of a composition
is defined as the complement (see
complement()
) of the reverse composition (seereversed()
) of.
An equivalent definition of the conjugate goes by saying that the ribbon shape of the conjugate of a composition
is the conjugate of the ribbon shape of
. (The ribbon shape of a composition is returned by
to_skew_partition()
.)This implementation uses the algorithm from mupad-combinat.
EXAMPLES:
sage: Composition([1, 1, 3, 1, 2, 1, 3]).conjugate() [1, 1, 3, 3, 1, 3]
The ribbon shape of the conjugate of
is the conjugate of the ribbon shape of
:
sage: all( I.conjugate().to_skew_partition() ....: == I.to_skew_partition().conjugate() ....: for I in Compositions(4) ) True
TESTS:
sage: parent(list(Compositions(1))[0].conjugate()) Compositions of 1 sage: parent(list(Compositions(0))[0].conjugate()) Compositions of 0
-
descents
(final_descent=False)¶ This gives one fewer than the partial sums of the composition.
This is here to maintain some sort of backward compatibility, even through the original implementation was broken (it gave the wrong answer). The same information can be found in
partial_sums()
.See also
INPUT:
final_descent
– (Default:False
) a boolean integer
OUTPUT:
- the list of partial sums of
self
with each part decremented by. This includes the sum of all entries when
final_descent
isTrue
.
EXAMPLES:
sage: c = Composition([2,1,3,2]) sage: c.descents() [1, 2, 5] sage: c.descents(final_descent=True) [1, 2, 5, 7]
-
fatten
(grouping)¶ Return the composition fatter than
self
, obtained by grouping together consecutive parts according togrouping
.INPUT:
grouping
– a composition whose sum is the length ofself
EXAMPLES:
Let us start with the composition:
sage: c = Composition([4,5,2,7,1])
With
grouping
equal to,
is left unchanged:
sage: c.fatten(Composition([1,1,1,1,1])) [4, 5, 2, 7, 1]
With
grouping
equal towhere
is the length of
, this yields the coarsest composition above
:
sage: c.fatten(Composition([5])) [19]
Other values for
grouping
yield (all the) other compositions coarser than:
sage: c.fatten(Composition([2,1,2])) [9, 2, 8] sage: c.fatten(Composition([3,1,1])) [11, 7, 1]
TESTS:
sage: Composition([]).fatten(Composition([])) [] sage: c.fatten(Composition([3,1,1])).__class__ == c.__class__ True
-
fatter
()¶ Return the set of compositions which are fatter than
self
.Complexity for generation:
memory,
time where
is the size of
self
andis the result.
EXAMPLES:
sage: C = Composition([4,5,2]).fatter() sage: C.cardinality() 4 sage: list(C) [[4, 5, 2], [4, 7], [9, 2], [11]]
Some extreme cases:
sage: list(Composition([5]).fatter()) [[5]] sage: list(Composition([]).fatter()) [[]] sage: list(Composition([1,1,1,1]).fatter()) == list(Compositions(4)) True
-
finer
()¶ Return the set of compositions which are finer than
self
.EXAMPLES:
sage: C = Composition([3,2]).finer() sage: C.cardinality() 8 sage: list(C) [[1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 2, 1, 1], [1, 2, 2], [2, 1, 1, 1], [2, 1, 2], [3, 1, 1], [3, 2]]
-
inf
(other, check=True)¶ Return the meet of
self
with a compositionother
of the same size.The meet of two compositions
and
of size
is the finest composition of
which is coarser than each of
and
. It can be described as the composition whose descent set is the intersection of the descent sets of
and
.
INPUT:
other
– composition of same size asself
check
– (default:True
) a Boolean determining whether to check the input compositions for having the same size
OUTPUT:
- the meet of the compositions
self
andother
EXAMPLES:
sage: Composition([3, 1, 1, 3, 1]).meet([4, 3, 2]) [4, 5] sage: Composition([9, 6]).meet([1, 3, 6, 3, 2]) [15] sage: Composition([9, 6]).meet([1, 3, 5, 1, 3, 2]) [9, 6] sage: Composition([1, 1, 1, 1, 1]).meet([3, 2]) [3, 2] sage: Composition([4, 2]).meet([3, 3]) [6] sage: Composition([]).meet([]) [] sage: Composition([1]).meet([1]) [1]
Let us verify on small examples that the meet of
and
is coarser than both of
and
:
sage: all( all( I.is_finer(I.meet(J)) and ....: J.is_finer(I.meet(J)) ....: for J in Compositions(4) ) ....: for I in Compositions(4) ) True
and is the finest composition to do so:
sage: all( all( all( I.meet(J).is_finer(K) ....: for K in I.fatter() ....: if J.is_finer(K) ) ....: for J in Compositions(3) ) ....: for I in Compositions(3) ) True
The descent set of the meet of
and
is the intersection of the descent sets of
and
:
sage: def test_meet(n): ....: return all( all( I.to_subset().intersection(J.to_subset()) ....: == I.meet(J).to_subset() ....: for J in Compositions(n) ) ....: for I in Compositions(n) ) sage: all( test_meet(n) for n in range(1, 5) ) True sage: all( test_meet(n) for n in range(5, 9) ) # long time True
TESTS:
sage: Composition([3, 1, 1, 3, 1]).meet([4, 3, 1]) Traceback (most recent call last): ... ValueError: [3, 1, 1, 3, 1] is not the same size as [4, 3, 1]
See also
AUTHORS:
- Darij Grinberg (2013-09-05)
-
is_finer
(co2)¶ Return
True
if the compositionself
is finer than the compositionco2
; otherwise, returnFalse
.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
-
join
(other, check=True)¶ Return the join of
self
with a compositionother
of the same size.The join of two compositions
and
of size
is the coarsest composition of
which refines each of
and
. It can be described as the composition whose descent set is the union of the descent sets of
and
. It is also the concatenation of
, where
is the ribbon decomposition of
with respect to
(see
ribbon_decomposition()
).INPUT:
other
– composition of same size asself
check
– (default:True
) a Boolean determining whether to check the input compositions for having the same size
OUTPUT:
- the join of the compositions
self
andother
EXAMPLES:
sage: Composition([3, 1, 1, 3, 1]).join([4, 3, 2]) [3, 1, 1, 2, 1, 1] sage: Composition([9, 6]).join([1, 3, 6, 3, 2]) [1, 3, 5, 1, 3, 2] sage: Composition([9, 6]).join([1, 3, 5, 1, 3, 2]) [1, 3, 5, 1, 3, 2] sage: Composition([1, 1, 1, 1, 1]).join([3, 2]) [1, 1, 1, 1, 1] sage: Composition([4, 2]).join([3, 3]) [3, 1, 2] sage: Composition([]).join([]) []
Let us verify on small examples that the join of
and
refines both of
and
:
sage: all( all( I.join(J).is_finer(I) and ....: I.join(J).is_finer(J) ....: for J in Compositions(4) ) ....: for I in Compositions(4) ) True
and is the coarsest composition to do so:
sage: all( all( all( K.is_finer(I.join(J)) ....: for K in I.finer() ....: if K.is_finer(J) ) ....: for J in Compositions(3) ) ....: for I in Compositions(3) ) True
Let us check that the join of
and
is indeed the conctenation of
, where
is the ribbon decomposition of
with respect to
:
sage: all( all( Composition.sum(I.ribbon_decomposition(J)[0]) ....: == I.join(J) for J in Compositions(4) ) ....: for I in Compositions(4) ) True
Also, the descent set of the join of
and
is the union of the descent sets of
and
:
sage: all( all( I.to_subset().union(J.to_subset()) ....: == I.join(J).to_subset() ....: for J in Compositions(4) ) ....: for I in Compositions(4) ) True
TESTS:
sage: Composition([3, 1, 1, 3, 1]).join([4, 3, 1]) Traceback (most recent call last): ... ValueError: [3, 1, 1, 3, 1] is not the same size as [4, 3, 1]
See also
AUTHORS:
- Darij Grinberg (2013-09-05)
-
major_index
()¶ Return the major index of
self
. The major index is defined as the sum of the descents.EXAMPLES:
sage: Composition([1, 1, 3, 1, 2, 1, 3]).major_index() 31
-
meet
(other, check=True)¶ Return the meet of
self
with a compositionother
of the same size.The meet of two compositions
and
of size
is the finest composition of
which is coarser than each of
and
. It can be described as the composition whose descent set is the intersection of the descent sets of
and
.
INPUT:
other
– composition of same size asself
check
– (default:True
) a Boolean determining whether to check the input compositions for having the same size
OUTPUT:
- the meet of the compositions
self
andother
EXAMPLES:
sage: Composition([3, 1, 1, 3, 1]).meet([4, 3, 2]) [4, 5] sage: Composition([9, 6]).meet([1, 3, 6, 3, 2]) [15] sage: Composition([9, 6]).meet([1, 3, 5, 1, 3, 2]) [9, 6] sage: Composition([1, 1, 1, 1, 1]).meet([3, 2]) [3, 2] sage: Composition([4, 2]).meet([3, 3]) [6] sage: Composition([]).meet([]) [] sage: Composition([1]).meet([1]) [1]
Let us verify on small examples that the meet of
and
is coarser than both of
and
:
sage: all( all( I.is_finer(I.meet(J)) and ....: J.is_finer(I.meet(J)) ....: for J in Compositions(4) ) ....: for I in Compositions(4) ) True
and is the finest composition to do so:
sage: all( all( all( I.meet(J).is_finer(K) ....: for K in I.fatter() ....: if J.is_finer(K) ) ....: for J in Compositions(3) ) ....: for I in Compositions(3) ) True
The descent set of the meet of
and
is the intersection of the descent sets of
and
:
sage: def test_meet(n): ....: return all( all( I.to_subset().intersection(J.to_subset()) ....: == I.meet(J).to_subset() ....: for J in Compositions(n) ) ....: for I in Compositions(n) ) sage: all( test_meet(n) for n in range(1, 5) ) True sage: all( test_meet(n) for n in range(5, 9) ) # long time True
TESTS:
sage: Composition([3, 1, 1, 3, 1]).meet([4, 3, 1]) Traceback (most recent call last): ... ValueError: [3, 1, 1, 3, 1] is not the same size as [4, 3, 1]
See also
AUTHORS:
- Darij Grinberg (2013-09-05)
-
near_concatenation
(other)¶ Return the near-concatenation of two nonempty compositions
self
andother
.The near-concatenation
of two nonempty compositions
and
is defined as the composition
, where
and
.
This method returns
None
if one of the two input compositions is empty.EXAMPLES:
sage: Composition([1, 1, 3]).near_concatenation(Composition([4, 1, 2])) [1, 1, 7, 1, 2] sage: Composition([6]).near_concatenation(Composition([1, 5])) [7, 5] sage: Composition([1, 5]).near_concatenation(Composition([6])) [1, 11]
TESTS:
sage: Composition([]).near_concatenation(Composition([])) sage: Composition([]).near_concatenation(Composition([2, 1])) sage: Composition([3, 2]).near_concatenation(Composition([]))
-
partial_sums
(final=True)¶ The partial sums of the sequence defined by the entries of the composition.
If
is a composition, then the partial sums of the entries of the composition are
.
INPUT:
final
– (default:True
) whether or not to include the final partial sum, which is always the size of the composition.
See also
EXAMPLES:
sage: Composition([1,1,3,1,2,1,3]).partial_sums() [1, 2, 5, 6, 8, 9, 12]
With
final = False
, the last partial sum is not included:sage: Composition([1,1,3,1,2,1,3]).partial_sums(final=False) [1, 2, 5, 6, 8, 9]
-
peaks
()¶ Return 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]
-
refinement_splitting
(J)¶ Return the refinement splitting of
self
according toJ
.INPUT:
J
– A composition such thatself
is finer thanJ
OUTPUT:
- the unique list of compositions
, obtained by splitting
, such that
for all
.
See also
EXAMPLES:
sage: Composition([1,2,2,1,1,2]).refinement_splitting([5,1,3]) [[1, 2, 2], [1], [1, 2]] sage: Composition([]).refinement_splitting([]) [] sage: Composition([3]).refinement_splitting([2]) Traceback (most recent call last): ... ValueError: compositions self (= [3]) and J (= [2]) must be of the same size sage: Composition([2,1]).refinement_splitting([1,2]) Traceback (most recent call last): ... ValueError: composition J (= [2, 1]) does not refine self (= [1, 2])
-
refinement_splitting_lengths
(J)¶ Return the lengths of the compositions in the refinement splitting of
self
according toJ
.See also
refinement_splitting()
for the definition of refinement splittingEXAMPLES:
sage: Composition([1,2,2,1,1,2]).refinement_splitting_lengths([5,1,3]) [3, 1, 2] sage: Composition([]).refinement_splitting_lengths([]) [] sage: Composition([3]).refinement_splitting_lengths([2]) Traceback (most recent call last): ... ValueError: compositions self (= [3]) and J (= [2]) must be of the same size sage: Composition([2,1]).refinement_splitting_lengths([1,2]) Traceback (most recent call last): ... ValueError: composition J (= [2, 1]) does not refine self (= [1, 2])
-
reversed
()¶ Return the reverse composition of
self
.The reverse composition of a composition
is defined as the composition
.
EXAMPLES:
sage: Composition([1, 1, 3, 1, 2, 1, 3]).reversed() [3, 1, 2, 1, 3, 1, 1]
-
ribbon_decomposition
(other, check=True)¶ Return a pair describing the ribbon decomposition of a composition
self
with respect to a compositionother
of the same size.If
and
are two compositions of the same nonzero size, then the ribbon decomposition of
with respect to
is defined as follows: Write
and
as
and
. Then, the equality
holds for a unique
-tuple
of compositions such that each
has size
and for a unique choice of
signs
each of which is either the concatenation sign
or the near-concatenation sign
(see
__add__()
andnear_concatenation()
for the definitions of these two signs). This-tuple and this choice of signs together are said to form the ribbon decomposition of
with respect to
. If
and
are empty, then the same definition applies, except that there are
rather than
signs.
See Section 4.8 of [NCSF1].
INPUT:
other
– composition of same size asself
check
– (default:True
) a Boolean determining whether to check the input compositions for having the same size
OUTPUT:
- a pair
(u, v)
, whereu
is a tuple of compositions (corresponding to the-tuple
in the above definition), and
v
is a tuple ofin the above definition, with a
standing for
and a
standing for
).
EXAMPLES:
sage: Composition([3, 1, 1, 3, 1]).ribbon_decomposition([4, 3, 2]) (([3, 1], [1, 2], [1, 1]), (0, 1)) sage: Composition([9, 6]).ribbon_decomposition([1, 3, 6, 3, 2]) (([1], [3], [5, 1], [3], [2]), (1, 1, 1, 1)) sage: Composition([9, 6]).ribbon_decomposition([1, 3, 5, 1, 3, 2]) (([1], [3], [5], [1], [3], [2]), (1, 1, 0, 1, 1)) sage: Composition([1, 1, 1, 1, 1]).ribbon_decomposition([3, 2]) (([1, 1, 1], [1, 1]), (0,)) sage: Composition([4, 2]).ribbon_decomposition([6]) (([4, 2],), ()) sage: Composition([]).ribbon_decomposition([]) ((), ())
Let us check that the defining property
is satisfied:
sage: def compose_back(u, v): ....: comp = u[0] ....: r = len(v) ....: if len(u) != r + 1: ....: raise ValueError("something is wrong") ....: for i in range(r): ....: if v[i] == 0: ....: comp += u[i + 1] ....: else: ....: comp = comp.near_concatenation(u[i + 1]) ....: return comp sage: all( all( all( compose_back(*(I.ribbon_decomposition(J))) == I ....: for J in Compositions(n) ) ....: for I in Compositions(n) ) ....: for n in range(1, 5) ) True
TESTS:
sage: Composition([3, 1, 1, 3, 1]).ribbon_decomposition([4, 3, 1]) Traceback (most recent call last): ... ValueError: [3, 1, 1, 3, 1] is not the same size as [4, 3, 1]
AUTHORS:
- Darij Grinberg (2013-08-29)
-
shuffle_product
(other, overlap=False)¶ The (overlapping) shuffles of
self
andother
.Suppose
and
are two compositions. A shuffle of
and
is a composition of length
that contains both
and
as subsequences.
More generally, an overlapping shuffle of
and
is obtained by distributing the elements of
and
(preserving the relative ordering of these elements) among the positions of an empty list; an element of
and an element of
are permitted to share the same position, in which case they are replaced by their sum. In particular, a shuffle of
and
is an overlapping shuffle of
and
.
INPUT:
other
– compositionoverlap
– boolean (default:False
); ifTrue
, the overlapping shuffle product is returned.
OUTPUT:
An enumerated set (allowing for mutliplicities)
EXAMPLES:
The shuffle product of
and
:
sage: alph = Composition([2,2]) sage: beta = Composition([1,1,3]) sage: S = alph.shuffle_product(beta); S Shuffle product of [2, 2] and [1, 1, 3] sage: S.list() [[2, 2, 1, 1, 3], [2, 1, 2, 1, 3], [2, 1, 1, 2, 3], [2, 1, 1, 3, 2], [1, 2, 2, 1, 3], [1, 2, 1, 2, 3], [1, 2, 1, 3, 2], [1, 1, 2, 2, 3], [1, 1, 2, 3, 2], [1, 1, 3, 2, 2]]
The overlapping shuffle product of
and
:
sage: alph = Composition([2,2]) sage: beta = Composition([1,1,3]) sage: O = alph.shuffle_product(beta, overlap=True); O Overlapping shuffle product of [2, 2] and [1, 1, 3] sage: O.list() [[2, 2, 1, 1, 3], [2, 1, 2, 1, 3], [2, 1, 1, 2, 3], [2, 1, 1, 3, 2], [1, 2, 2, 1, 3], [1, 2, 1, 2, 3], [1, 2, 1, 3, 2], [1, 1, 2, 2, 3], [1, 1, 2, 3, 2], [1, 1, 3, 2, 2], [3, 2, 1, 3], [2, 3, 1, 3], [3, 1, 2, 3], [2, 1, 3, 3], [3, 1, 3, 2], [2, 1, 1, 5], [1, 3, 2, 3], [1, 2, 3, 3], [1, 3, 3, 2], [1, 2, 1, 5], [1, 1, 5, 2], [1, 1, 2, 5], [3, 3, 3], [3, 1, 5], [1, 3, 5]]
Note that the shuffle product of two compositions can include the same composition more than once since a composition can be a shuffle of two compositions in several ways. For example:
sage: S = Composition([1]).shuffle_product([1]); S Shuffle product of [1] and [1] sage: S.list() [[1, 1], [1, 1]] sage: O = Composition([1]).shuffle_product([1], overlap=True); O Overlapping shuffle product of [1] and [1] sage: O.list() [[1, 1], [1, 1], [2]]
TESTS:
sage: Composition([]).shuffle_product([]).list() [[]]
-
size
()¶ Return the size of
self
, that is the sum of its parts.EXAMPLES:
sage: Composition([7,1,3]).size() 11
-
static
sum
(compositions)¶ Return the concatenation of the given compositions.
INPUT:
compositions
– a list (or iterable) of compositions
EXAMPLES:
sage: Composition.sum([Composition([1, 1, 3]), Composition([4, 1, 2]), Composition([3,1])]) [1, 1, 3, 4, 1, 2, 3, 1]
Any iterable can be provided as input:
sage: Composition.sum([Composition([i,i]) for i in [4,1,3]]) [4, 4, 1, 1, 3, 3]
Empty inputs are handled gracefully:
sage: Composition.sum([]) == Composition([]) True
-
sup
(other, check=True)¶ Return the join of
self
with a compositionother
of the same size.The join of two compositions
and
of size
is the coarsest composition of
which refines each of
and
. It can be described as the composition whose descent set is the union of the descent sets of
and
. It is also the concatenation of
, where
is the ribbon decomposition of
with respect to
(see
ribbon_decomposition()
).INPUT:
other
– composition of same size asself
check
– (default:True
) a Boolean determining whether to check the input compositions for having the same size
OUTPUT:
- the join of the compositions
self
andother
EXAMPLES:
sage: Composition([3, 1, 1, 3, 1]).join([4, 3, 2]) [3, 1, 1, 2, 1, 1] sage: Composition([9, 6]).join([1, 3, 6, 3, 2]) [1, 3, 5, 1, 3, 2] sage: Composition([9, 6]).join([1, 3, 5, 1, 3, 2]) [1, 3, 5, 1, 3, 2] sage: Composition([1, 1, 1, 1, 1]).join([3, 2]) [1, 1, 1, 1, 1] sage: Composition([4, 2]).join([3, 3]) [3, 1, 2] sage: Composition([]).join([]) []
Let us verify on small examples that the join of
and
refines both of
and
:
sage: all( all( I.join(J).is_finer(I) and ....: I.join(J).is_finer(J) ....: for J in Compositions(4) ) ....: for I in Compositions(4) ) True
and is the coarsest composition to do so:
sage: all( all( all( K.is_finer(I.join(J)) ....: for K in I.finer() ....: if K.is_finer(J) ) ....: for J in Compositions(3) ) ....: for I in Compositions(3) ) True
Let us check that the join of
and
is indeed the conctenation of
, where
is the ribbon decomposition of
with respect to
:
sage: all( all( Composition.sum(I.ribbon_decomposition(J)[0]) ....: == I.join(J) for J in Compositions(4) ) ....: for I in Compositions(4) ) True
Also, the descent set of the join of
and
is the union of the descent sets of
and
:
sage: all( all( I.to_subset().union(J.to_subset()) ....: == I.join(J).to_subset() ....: for J in Compositions(4) ) ....: for I in Compositions(4) ) True
TESTS:
sage: Composition([3, 1, 1, 3, 1]).join([4, 3, 1]) Traceback (most recent call last): ... ValueError: [3, 1, 1, 3, 1] is not the same size as [4, 3, 1]
See also
AUTHORS:
- Darij Grinberg (2013-09-05)
-
to_code
()¶ Return the code of the composition
self
. The code of a compositionis a list of length
of 1s and 0s such that there is a 1 wherever a new part starts. (Exceptional case: When the composition is empty, the code is
[0]
.)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]
-
to_partition
()¶ Return the partition obtained by sorting
self
into decreasing order.EXAMPLES:
sage: Composition([2,1,3]).to_partition() [3, 2, 1] sage: Composition([4,2,2]).to_partition() [4, 2, 2] sage: Composition([]).to_partition() []
-
to_skew_partition
(overlap=1)¶ Return the skew partition obtained from
self
. This is a skew partition whose rows have the entries ofself
as their length, taken in reverse order (so the first entry ofself
is the length of the lowermost row, etc.). The parameteroverlap
indicates the number of cells on each row that are directly below cells of the previous row. When it is set to(its default value), the result is the ribbon shape of
self
.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] sage: Composition([]).to_skew_partition() [] / [] sage: Composition([1,2]).to_skew_partition() [2, 1] / [] sage: Composition([2,1]).to_skew_partition() [2, 2] / [1]
-
to_subset
(final=False)¶ The subset corresponding to
self
under the bijection (see below) between compositions ofand subsets of
.
The bijection maps a composition
of
to
.
INPUT:
final
– (default:False
) whether or not to include the final partial sum, which is always the size of the composition.
See also
EXAMPLES:
sage: Composition([1,1,3,1,2,1,3]).to_subset() {1, 2, 5, 6, 8, 9} sage: for I in Compositions(3): print I.to_subset() {1, 2} {1} {2} {}
With
final=True
, the sum of all the elements of the composition is included in the subset:sage: Composition([1,1,3,1,2,1,3]).to_subset(final=True) {1, 2, 5, 6, 8, 9, 12}
TESTS:
We verify that
to_subset
is indeed a bijection for compositions of size:
sage: n = 8 sage: all(Composition(from_subset=(S, n)).to_subset() == S \ ... for S in Subsets(n-1)) True sage: all(Composition(from_subset=(I.to_subset(), n)) == I \ ... for I in Compositions(n)) True
-
wll_gt
(co2)¶ Return
True
if the compositionself
is greater than the compositionco2
with respect to the wll-ordering; otherwise, returnFalse
.The wll-ordering is a total order on the set of all compositions defined as follows: A composition
is greater than a composition
if and only if one of the following conditions holds:
- The size of
is greater than the size of
.
- The size of
equals the size of
, but the length of
is greater than the length of
.
- The size of
equals the size of
, and the length of
equals the length of
, but
is lexicographically greater than
.
(“wll-ordering” is short for “weight, length, lexicographic ordering”.)
EXAMPLES:
sage: Composition([4,1,2]).wll_gt([3,1,3]) True sage: Composition([7]).wll_gt([4,1,2]) False sage: Composition([8]).wll_gt([4,1,2]) True sage: Composition([3,2,2,2]).wll_gt([5,2]) True sage: Composition([]).wll_gt([3]) False sage: Composition([2,1]).wll_gt([2,1]) False sage: Composition([2,2,2]).wll_gt([4,2]) True sage: Composition([4,2]).wll_gt([2,2,2]) False sage: Composition([1,1,2]).wll_gt([2,2]) True sage: Composition([2,2]).wll_gt([1,3]) True sage: Composition([2,1,2]).wll_gt([]) True
- The size of
-
-
class
sage.combinat.composition.
Compositions
(is_infinite=False)¶ Bases:
sage.structure.parent.Parent
,sage.structure.unique_representation.UniqueRepresentation
Set of integer compositions.
A composition
of a nonnegative integer
is a list of positive integers with total sum
.
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
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
is specified, it returns the class of compositions of
:
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
.TESTS:
sage: C = Compositions(4, length=2) sage: C == loads(dumps(C)) True sage: Compositions(6, min_part=2, length=3) Compositions of the integer 6 satisfying constraints length=3, min_part=2 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: 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 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]] sage: Compositions(4, max_part=2).list() [[2, 2], [2, 1, 1], [1, 2, 1], [1, 1, 2], [1, 1, 1, 1]] sage: Compositions(4, min_part=2).list() [[4], [2, 2]] sage: Compositions(4, outer=[3,1,2]).list() [[3, 1], [2, 1, 1], [1, 1, 2]] sage: Compositions(3, outer = Composition([3,2])).list() [[3], [2, 1], [1, 2]] sage: Compositions(4, outer=[1,oo,1]).list() [[1, 3], [1, 2, 1]] sage: Compositions(4, inner=[1,1,1]).list() [[2, 1, 1], [1, 2, 1], [1, 1, 2], [1, 1, 1, 1]] sage: Compositions(4, inner=Composition([1,2])).list() [[2, 2], [1, 3], [1, 2, 1]] sage: Compositions(4, min_slope=0).list() [[4], [2, 2], [1, 3], [1, 1, 2], [1, 1, 1, 1]] 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]] 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]] 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]]
-
Element
¶ alias of
Composition
-
from_code
(code)¶ Return the composition from its code. The code of a composition
is a list of length
consisting of 1s and 0s such that there is a 1 wherever a new part starts. (Exceptional case: When the composition is empty, the code is
[0]
.)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] sage: Compositions().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: Compositions().from_code(_) [3, 1, 2, 3, 5]
-
from_descents
(descents, nps=None)¶ Return a composition from the list of descents.
INPUT:
descents
– an iterablenps
– (default:None
) an integer orNone
OUTPUT:
- The composition of
nps
whose descents are listed indescents
, assuming thatnps
is notNone
(otherwise, the last element ofdescents
is removed fromdescents
, andnps
is set to be this last element plus 1).
EXAMPLES:
sage: [x-1 for x in Composition([1, 1, 3, 4, 3]).to_subset()] [0, 1, 4, 8] sage: Compositions().from_descents([1,0,4,8],12) [1, 1, 3, 4, 3] sage: Compositions().from_descents([1,0,4,8,11]) [1, 1, 3, 4, 3]
-
from_subset
(S, n)¶ The composition of
corresponding to the subset
S
ofunder the bijection that maps the composition
of
to the subset
(see
Composition.to_subset()
).INPUT:
S
– an iterable, a subset ofn
– an integer
EXAMPLES:
sage: Compositions().from_subset([2,1,5,9], 12) [1, 1, 3, 4, 3] sage: Compositions().from_subset({2,1,5,9}, 12) [1, 1, 3, 4, 3] sage: Compositions().from_subset([], 12) [12] sage: Compositions().from_subset([], 0) []
TESTS:
sage: Compositions().from_subset([2,1,5,9],9) Traceback (most recent call last): ... ValueError: S (=[1, 2, 5, 9]) is not a subset of {1, ..., 8}
-
-
class
sage.combinat.composition.
Compositions_all
¶ Bases:
sage.combinat.composition.Compositions
Class of all compositions.
-
subset
(size=None)¶ Return the set of compositions of the given size.
EXAMPLES:
sage: C = Compositions() sage: C.subset(4) Compositions of 4 sage: C.subset(size=3) Compositions of 3
-
-
class
sage.combinat.composition.
Compositions_constraints
(n=None, length=None, min_length=0, max_length=inf, floor=None, ceiling=None, min_part=0, max_part=inf, min_slope=-inf, max_slope=inf, min_sum=0, max_sum=inf, name=None, category=None, element_constructor=None, element_class=None, global_options=None, check=True)¶ Bases:
sage.combinat.integer_list.IntegerListsLex
Initialize
self
.TESTS:
sage: C = IntegerListsLex(2, length=3) sage: C == loads(dumps(C)) True sage: C == loads(dumps(C)) # this did fail at some point, really! True sage: C is loads(dumps(C)) # todo: not implemented True sage: C.cardinality().parent() is ZZ True sage: TestSuite(C).run() sage: IntegerListsLex(min_sum=Infinity).list() Traceback (most recent call last): ... TypeError: unable to coerce <class 'sage.rings.infinity.PlusInfinity'> to an integer sage: IntegerListsLex(min_sum=1.4).list() Traceback (most recent call last): ... TypeError: Attempt to coerce non-integral RealNumber to Integer
-
class
sage.combinat.composition.
Compositions_n
(n)¶ Bases:
sage.combinat.composition.Compositions
Class of compositions of a fixed
.
-
cardinality
()¶ Return the number of compositions of
.
TESTS:
sage: Compositions(3).cardinality() 4 sage: Compositions(0).cardinality() 1
-
random_element
()¶ Return a random
Composition
with uniform probability.This method generates a random binary word starting with a 1 and then uses the bijection between compositions and their code.
EXAMPLES:
sage: Compositions(5).random_element() # random [2, 1, 1, 1] sage: Compositions(0).random_element() [] sage: Compositions(1).random_element() [1]
TESTS:
sage: all([Compositions(10).random_element() in Compositions(10) for i in range(20)]) True
-