Module composition

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).count()
    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
  equaivalent 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 constaints.  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 differnce 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:
    --Mike Hansen
    --MuPAD-Combinat developers (for algorithms and design inspiration)

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 combinatorial class of compositions.

EXAMPLES:
  If n is not specificied, 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).count()
    4

  In addition, the following constaints 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]]

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]

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]