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\).

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, 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.

sage.combinat.composition.Compositions_all

Class of all compositions.

class sage.combinat.composition.Compositions_constraints(*args, **kwds)

Bases: sage.combinat.integer_lists.invlex.IntegerListsLex

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.