Integer compositions

A composition c of a nonnegative integer n is a list of positive integers (the parts of the compositions) 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
class sage.combinat.composition.Composition(parent, lst)

Bases: sage.combinat.combinat.CombinatorialObject, sage.structure.element.Element

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]
complement(*args, **kwds)

Return the complement composition of self. The complement is the reverse of the conjugate composition of self.

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(*args, **kwds)

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]
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

partial_sums()

INPUT:

  • final_descent – (Default: False) a boolean integer

OUTPUT:

  • Returns the list of partial sums of self with each part subtracted by 1. This includes the sum of all entries when final_descent is True.

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 to grouping.

INPUT:

  • grouping – a composition whose sum is the length of self

EXAMPLES:

Let us start with the composition:

sage: c = Composition([4,5,2,7,1])

With grouping equal to (1, \ldots, 1), c is left unchanged:

sage: c.fatten(Composition([1,1,1,1,1]))
[4, 5, 2, 7, 1]

With grouping equal to (\ell) where \ell is the length of self, this yields the coarser composition above c:

sage: c.fatten(Composition([5]))
[19]

Other values for grouping yield (all the) other compositions coarser to c:

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: O(|c|) memory, O(|r|) time where |c| is the size of self and r is 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]]
is_finer(co2)

Return 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
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
partial_sums(final=True)

The partial sums of the sequence defined by the entries of the composition.

If I = (i_1, \ldots, i_m) is a composition, then the partial sums of the entries of the composition are [i_1, i_1 + i_2, \ldots, i_1 + i_2 + \cdots + i_{m}].

INPUT:

  • final – (default: True) whether or not to include the final partial sum, which is always the size of the composition.

See also

to_subset()

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(*args, **kwds)

Deprecated: Use refinement_splitting_lengths() instead. See trac ticket #13243 for details.

refinement_splitting(J)

Return the refinement splitting of self according to J.

INPUT:

  • J – A composition such that I is finer than J

OUTPUT:

  • the unique list of compositions (I^{(p)})_{p=1\ldots m}, obtained by splitting I, such that |I^{(p)}| = J_p for all p = 1, \ldots, m.

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 I=self according to J.

See also

refinement_splitting() for the definition of refinement splitting

EXAMPLES:

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(*args, **kwds)

Return the reverse composition of self.

EXAMPLES:

sage: Composition([1, 1, 3, 1, 2, 1, 3]).reversed()
[3, 1, 2, 1, 3, 1, 1]
shuffle_product(other, overlap=False)

The (overlapping) shuffles of self and other.

Suppose I = (i_1, \ldots, i_k) and J = (j_1, \ldots, j_l) are two compositions. A shuffle of I and J is a composition of length k + l that contains both I and J as subsequences.

More generally, an overlapping shuffle of I and J is obtained by distributing the elements of I and J (preserving the relative ordering of these elements) among the positions of an empty list; an element of I and an element of J are permitted to share the same position, in which case they are replaced by their sum. In particular, a shuffle of I and J is an overlapping shuffle of I and J.

INPUT:

  • other – composition
  • overlap – boolean (default: False); if True, the overlapping shuffle product is returned.

OUTPUT:

An enumerated set (allowing for mutliplicities)

EXAMPLES:

The shuffle product of [2,2] and [1,1,3]:

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 [2,2] and [1,1,3]:

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
to_code()

Return 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]
to_partition(*args, **kwds)

Sorts self into decreasing order and returns the corresponding partition.

EXAMPLES:

sage: Composition([2,1,3]).to_partition()
[3, 2, 1]
sage: Composition([4,2,2]).to_partition()
[4, 2, 2]
to_skew_partition(overlap=1)

Return the skew partition obtained from self. The parameter overlap indicates the number of cells that are covered by cells 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]
to_subset(final=False)

The subset corresponding to self under the bijection (see below) between compositions of n and subsets of \{1, 2, \ldots, n-1\}.

The bijection maps a composition (i_1, \ldots, i_k) of n to \{i_1, i_1 + i_2, i_1 + i_2 + i_3, \ldots, i_1 + \cdots + i_{k-1}\}.

INPUT:

  • final – (default: False) whether or not to include the final partial sum, which is always the size of the composition.

See also

partial_sums()

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 n = 8:

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
class sage.combinat.composition.Compositions(is_infinite=False)

Bases: sage.structure.parent.Parent, sage.structure.unique_representation.UniqueRepresentation

Set of integer compositions.

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]

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

Note that the given constraints should be compatible:

sage: [4,2] in Compositions(6, inner=[2,2], min_part=3)
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()
[[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 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()
[[3, 1], [2, 2], [1, 3]]

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: list(Compositions(4, outer=[3,1,2]))
[[3, 1], [2, 1, 1], [1, 1, 2]]

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, 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 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()
[[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 using IntegerVectors 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 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]
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)

Returns a composition from the list of descents.

INPUT:

  • descents – an iterable
  • nps – (default: None) an integer or None; if None, then nps is taken to be 1 plus the maximum element of descents.

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 n corresponding to the subset S 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 Composition.to_subset()).

INPUT:

  • S – an iterable, a subset of n-1
  • n – 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]

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, length=None, min_length=0, max_length=inf, floor=None, ceiling=None, min_part=0, max_part=inf, min_slope=-inf, max_slope=inf, name=None, element_constructor=None, element_class=None, global_options=None)

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()
class sage.combinat.composition.Compositions_n(n)

Bases: sage.combinat.composition.Compositions

Class of compositions of a fixed n.

cardinality()

Return the number of compositions of n.

TESTS:

sage: Compositions(3).cardinality()
4
sage: Compositions(0).cardinality()
1
sage.combinat.composition.composition_from_subset(S, n)

This has been deprecated in trac ticket #14063. Use Compositions.from_subset() instead.

EXAMPLES:

sage: from sage.combinat.composition import composition_from_subset
sage: composition_from_subset([2,1,5,9], 12)
doctest:1: DeprecationWarning: composition_from_subset is deprecated. Use Compositions().from_subset instead.
See http://trac.sagemath.org/14063 for details.
[1, 1, 3, 4, 3]
sage.combinat.composition.from_code(code)

This has been deprecated in trac ticket #14063. Use Compositions.from_code() instead.

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(_)
doctest:1: DeprecationWarning: from_code is deprecated. Use Compositions().from_code instead.
See http://trac.sagemath.org/14063 for details.
[4, 1, 2, 3, 5]
sage.combinat.composition.from_descents(descents, nps=None)

This has been deprecated in trac ticket #14063. Use Compositions.from_descents() instead.

EXAMPLES:

sage: [x-1 for x in Composition([1, 1, 3, 4, 3]).to_subset()]
[0, 1, 4, 8]
sage: sage.combinat.composition.from_descents([1,0,4,8],12)
doctest:1: DeprecationWarning: from_descents is deprecated. Use Compositions().from_descents instead.
See http://trac.sagemath.org/14063 for details.
[1, 1, 3, 4, 3]

Previous topic

Signed Compositions

Next topic

Cores

This Page