Metadata-Version: 2.4
Name: combol
Version: 0.1.7
Classifier: Programming Language :: Rust
Classifier: Programming Language :: Python :: 3.12
Classifier: License :: OSI Approved :: GNU General Public License v3 (GPLv3)
Classifier: Topic :: Scientific/Engineering
Classifier: Topic :: Scientific/Engineering :: Mathematics
Requires-Dist: symbolica
Requires-Dist: numpy
Requires-Dist: paganini
Requires-Dist: cvxpy==1.8.2
Requires-Dist: ecos
License-File: LICENSE
Summary: CombOL - the Combinatorial Objects Library.
Keywords: combinatorics,analytic combinatorics,generating function,counting sequence,enumeration,random sampling,boltzmann sampling
Author-email: Casper Asbjørn Eriksen <casbjorn@imada.sdu.dk>
Maintainer-email: Casper Asbjørn Eriksen <casbjorn@imada.sdu.dk>
License-Expression: GPL-3.0-only
Requires-Python: >=3.12
Description-Content-Type: text/markdown; charset=UTF-8; variant=GFM

<img alt="combol_wordmark.svg" height="120" src="docs/assets/combol_wordmark.svg"/>

### _The Combinatorial Objects Library_

---

## Introduction

CombOL is an open-source library for the enumeration and Boltzmann sampling of
combinatorial classes, written in Rust and Python.

Classes can be specified programmatically through Python, via JSON files, or parsed from a concise string syntax, and
may be defined in terms of an arbitrary number of parameters. From a specification, CombOL automatically derives the
generating functions, enabling the generation of counting sequences. The library supports exact and approximate-size
Boltzmann rejection sampling with automatic parameter tuning to target specific sizes. In addition to implementing
established methods, CombOL features a novel early rejection scheme, as well as guaranteed statistical correctness by
dynamically increasing the numerical precision, eliminating bias due to floating-point rounding errors.

Through the Python interface, users can define application-specific functions for combinatorial operators, enabling
direct sampling of domain objects such as graphs, chemical structure representations, or other complex data types.

---

## Paper

If you find CombOL helpful in your research, please cite the associated paper.

> **CombOL: a Library for Practical Enumeration and Boltzmann Sampling of Combinatorial Classes**
>
> *Casper Asbjørn Eriksen, Daniel Merkle*
>
> Accepted for publication in proceedings of [ICMS 2026](https://icms-conference.org/2026/index.html).
>
> Preprint: https://doi.org/10.48550/arXiv.2605.04629


---

## Tutorial

### Quickstart

```python
import combol

# Classes are specified by parsing a string written in syntax similar to `combstruct`.
btrees = combol.parse('B = z + (z * B * B)')

# CombOL can produce the counting sequence for univariate or multivariate classes.
counting_sequence = combol.enumerate(10)  # Poly: z + z^3 + 2z^5 + 5z^7 + ...

# We can also sample structures from the class.
sampler = btrees.sampler(0.2)
sampled_structure = sampler.sample()  # Product(z, Product(z, z, z), z)
```

This creates a combinatorial class object which can be used for various purposes.

### Specifying classes

Classes are specified by parsing strings with a syntax similar to that of the `combstruct` maple package.
In this syntax, classes must start with uppercase letters, and variables with lowercase letters.

The table below shows the supported combinatorial constructions and their syntax.

We can also define classes that depend on each other, e.g.

```python
mappings = combol.parse([
    'Y = CYC(C)',
    'C = z * SET(C)'
])
```

When a variable is used in a class definition, an atom with size 1 in that variable is implicitly added.
We can also define atoms explicitly. In the following example, we define the class of unary-binary trees,
marking binary nodes with an additional parameter `u`:

```python
ubtrees = combol.parse([
    'leafnode = atom(z: 1)',
    'unarynode = atom(z: 1)',
    'binarynode = atom(z: 1, u: 1)',
    'T = leafnode + (unarynode * T) + (binarynode * T * T)'
])
```

Here, we specified two different atoms with the same size.
This can useful for the structure mapping feature, described below.

### Enumeration

We can enumerate the class by calling `enumerate`. The argument is the maximum power to which the generating function is
expanded.
The result is a `Poly` object, which may be a `UnivariatePolynomial` if the class is univariate.

```python
btree_poly = btree.enumerate(10)
btree_poly.get_coefficients()  # -> [0, 1, 0, 1, 0, 2, 0, 5, 0, 14, 0]
```

For multivariate classes, the terms cannot be represented as a simple list.
Instead, the coefficients are stored as a list of monomials, each represented as a tuple of the variables with
exponents, and the coefficent.

### Sampling

To sample from a class, a sampler object needs to be created, instantiated with the desired values for the control
parameter(s).

```python
# Here, we define a sampler for z = 0.2
btree_sampler = btrees.sampler(0.2)
btree_sampler.sample()  # -> Product(z, Product(z, z, z), z)
```

By default, the output of the sampler will be an abstract tree-like representation of the sampled structure, such as
`Product(z, Product(z, z, z), z)`.

Note that For multivariate classes, the control parameter must be given for each variable, e.g.:

```python
ubtree_sampler = ubtrees.sampler({'z': 0.3, 'u': 0.2})
```

If structures within a range of sizes is desired, CombOL can perform rejection sampling (with an early rejection method
described in the paper) by setting the desired bounds, e.g.:

```python
btree_sampler.sample(100, bounds_upper=100)
btree_sampler.sample(100, bounds_lower=85, bounds_upper=115)
ubtree_sampler.sample(100, bounds_lower={'z': 10, 'u': 10}, bounds_upper={'z': 100, 'u': None})
```

### Control parameter tuning

The number of expected rejections can be significantly reduced by selecting the control paramters carefully.
CombOL supports automatic parameter tuning, e.g.:

```python
btree_params = btrees.tune_control_parameters(target_size={'z': 100})
ubtree_params = ubtrees.tune_control_parameters(target_size={'z': 100, 'u': 40})

# Sample with tuned variables
tuned_sampler = btrees.sampler(btree_params)
tuned_sampler.sample(1000)
```

Here, tuning a variable to `None` produces a singlular sampler in that variable.

### Structure Mappings

For domain-specific applications, CombOL suppports the mapping of structures to arbitrary domain objects.
The user just has to define the _bijection_ by specifying which objects correspond to the atoms, and how the
combinatorial constructions act on these objects.

To do this, subclass the `StructureBuilder` class.
Here, we define a bijection that produces Newick-formatted string representations of the sampled trees:

```python
class NewickNotationBuilder(StructureBuilder[str, str]):
    def atom(self, atom: Atom) -> str:
        return atom.key

    @classmethod
    def product(cls, node: SpecificationNodeConstructor, children: list[str]) -> str:
        # Assumed first given structure is internal node, the rest are children.
        return ('(' + ','.join(children[1:]) + ')' + children[0]) if len(children) > 1 else children[0]

    @classmethod
    def sequence(cls, node: SpecificationNodeConstructor, children: list[str]) -> str:
        return ','.join(children)
```

Now, we can use this bijection to directly sample Newick-formatted strings:

```python
newick_tree = btree_sampler.sample(1, bounds_lower=4, structure_builder=NewickNotationBuilder())
# -> (z,(z,z)z)z
```

This can of course also be applied to other domain objects, for instance chemical structures.
CombOL will only apply the defined bijection on accepted and completed sampling attempts, so no cycles are wasted
constructing structures which are going to be rejected.

Notice that we subclass `StructureBuilder` with two generic paramters, `T` and `TFinal`.
In most cases, these will be the same type (as in our example ablove), but in some cases, different intermediate and
final types may be needed.
In this case, the `finalize` method needs to be implemented, taking an object of type `T` and returning a `TFinal`.

---

## Combinatorial Constructions

CombOL supports the following combinatorial constructions:

| Construction          | Semantics                                                 | CombOL         | Enumeration | Sampling | Parameter Tuning |
|-----------------------|-----------------------------------------------------------|----------------|-------------|----------|------------------|
| **Disjoint Union**    | A structure chosen from A or B                            | `A + B`        | ✓           | ✓        | ✓                |
| **Cartesian Product** | A tuple of structures (a,b)                               | `A * B`        | ✓           | ✓        | ✓                |
| **Difference**        | A structure in A \ B                                      | `A \ B`        | ✓           |          |                  |
| **Diagonal**          | k identical structures from A                             | `DIAG_k(A)`    | ✓           |          |                  |
| **Sequence**          | A (possibly empty) ordered sequence of structures from A  |                |             |          |                  |
| - Unbounded           |                                                           | `SEQ(A)`       | ✓           | ✓        | ✓                |
| - Exact               |                                                           | `SEQ_k(A)`     | ✓           | ✓        | ✓                |
| - Lower bounded       |                                                           | `SEQ_>=k(A)`   | ✓           | ✓        | ✓                |
| - Upper bounded       |                                                           | `SEQ_<=k(A)`   | ✓           | ✓        | ✓                |
| - Range bounded       |                                                           | `SEQ_k..l(A)`  | ✓           | ✓        |                  |
| **Cycle**             | A sequence of structures from A, taken up to cyclic shift |                |             |          |                  |
| - Unbounded           |                                                           | `CYC(A)`       |             |          |                  |
| - Exact               |                                                           | `CYC_k(A)`     | ✓, Up to 4  |          | ✓                |
| - Lower bounded       |                                                           | `CYC_>=k(A)`   |             |          |                  |
| - Upper bounded       |                                                           | `CYC_<=k(A)`   | ✓, Up to 4  |          |                  |
| - Range bounded       |                                                           | `CYC_k..l(A)`  | ✓, Up to 4  |          |                  |
| **Multiset**          | A sequence of structures from A, taken up to permutation  |                |             |          |                  |
| - Unbounded           |                                                           | `MSET(A)`      |             |          | ✓                |
| - Exact               |                                                           | `MSET_k(A)`    | ✓, Up to 4  |          | ✓                |
| - Lower bounded       |                                                           | `MSET_>=k(A)`  |             |          |                  |
| - Upper bounded       |                                                           | `MSET_<=k(A)`  | ✓, Up to 4  |          |                  |
| - Range bounded       |                                                           | `MSET_k..l(A)` | ✓, Up to 4  |          |                  |

Support for more combinations of constructors and constraints is planned.
Parameter tuning is provided by the [Paganini](github.com/maciej-bendkowski/paganini) library.

---
