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')
>>> rng_seed(0xDEADBEEF)  # For reproducibility

>>> 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.add_rule(C, Seq(Nat, geq=1))
>>> 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)
       **
      **
     **
     *
    **
    *