# usainboltz.sage_examples.composition¶

## Integer compositions¶

An integer composition of a positive integer $$n$$ is a list of positive integers $$k_1, k_2, \ldots, k_r$$ such that $$\sum_i k_i = n$$. Using the value of an integer as its size, we can identify the class of positive integers with the class of non-empty sequences of atoms Seq(z, geq=1) by identifying n with the unique list of length n:

>>> from usainboltz import *
>>> from usainboltz.generator import rng_seed
>>> import warnings; warnings.filterwarnings("ignore", category=UserWarning, module='cvxpy.problems.problem')

>>> z = Atom()
>>> Nat = RuleName("Nat")
>>> grammar = Grammar({Nat: Seq(z, geq=1)})


Thus, integer partitions are non-empty sequences of integers:

>>> C = RuleName("C")
>>> grammar
{
C : Seq(Nat, geq = 1),
Nat : Seq(z, geq = 1)
}


Since the generating function of compositions is rational, one cannot use a singular sampler. But instead, one can ask the generator to tune its oracle to target a specific size (in expectation):

>>> generator = Generator(
...     grammar, C, expectations={z: 10}
... )


Finally, we define an appropriate builder that apply the bijection between lists and integers:

>>> def build_nat(l):
...     return len(l)
>>> generator.set_builder(Nat, build_nat)

>>> from sage.all import Composition
>>> def build_composition(l):
...     return Composition(l)
>>> generator.set_builder(C, build_composition)


Now we can generate sage compositions: # noqa

>>> res = generator.sample((10, 20))
>>> composition = res.obj
>>> composition.parent()
Compositions of non-negative integers
>>> composition
[1, 2, 1, 2, 2, 2]
>>> from builtins import sum
>>> 10 <= sum(composition) <= 20
True
>>> ascii_art(composition)
**
**
**
*
**
*