# Tilings

Tilings is a library for working with gridded permutations and tilings.

## Installing

To install `tilings` on your system, run:

``````pip install tilings
``````

It is also possible to install `tilings` in development mode to work on the source code, in which case you run the following after cloning the repository:

``````./setup.py develop
``````

To run the unit tests:

``````./setup.py test
``````

## What are gridded permutations and tilings?

We will be brief in our definitions here, for more details see Christian Bean’s PhD thesis.

A `gridded permutation` is a pair `(π, P)` where `π` is a permutation and `P` is a tuple of cells, called the positions, that denote the cells in which the points of `π` are drawn on a grid. Let `G` denote the set of all gridded permutations. Containment of gridded permutations is defined the same as containment of permutations, except including the preservation of the cells.

A `tiling` is a triple `T = ((n, m), O, R)`, where `n` and `m` are positive integers, `O` is a set of gridded permutations called `obstructions`, and `R` is a set of sets of gridded permutations called `requirements`.

We say a gridded permutations avoids a set of gridded permutations if it avoids all of the permutations in the set, otherwise it contains the set. To contain a set, therefore, means contains at least one in the set. The set of gridded permutations on a tiling `Grid(T)` is the set of all gridded permutations in the `n x m` grid that avoids `O` and contains each set `r` in `R`.

## Using tilings

Once you’ve installed `tilings`, it can be imported by a Python script or an interactive Python session, just like any other Python library:

``````>>> from tilings import *
``````

Importing `*` from it supplies you with the ‘GriddedPerm’, ‘Obstruction’, ‘Requirement’, and ‘Tiling’ classes.

As above, a gridded permutation is a pair `(π, P)` where `π` is a permutation and `P` is a tuple of cells. The permutation is assumed to be a `Perm` from the `permuta` Python library. Not every tuple of cells is a valid position for a given permutation. This can be checked using the `contradictory` method.

``````>>> from permuta import Perm
>>> gp = GriddedPerm(Perm((0, 2, 1)), ((0, 0), (0, 0), (1, 0)))
False
>>> gp = GriddedPerm(Perm((0, 1, 2)), ((0, 0), (0, 1), (0, 0)))
True
``````

A `Tiling` is created with an iterable of `Obstruction` and an iterable of `Requirement` lists. It is assumed that all cells not mentioned in some obstruction or requirement is empty. You can print the tiling to get an overview of the tiling created. In this example, we have a tiling that corresponds to non-empty permutation avoiding `123`.

``````>>> obstructions = [Obstruction.single_cell(Perm((0, 1)), (1, 1)),
...                 Obstruction.single_cell(Perm((1, 0)), (1, 1)),
...                 Obstruction.single_cell(Perm((0, 1)), (0, 0)),
...                 Obstruction.single_cell(Perm((0, 1, 2)), (2, 0)),
...                 Obstruction(Perm((0, 1, 2)), ((0, 0), (2, 0), (2, 0)))]
>>> requirements = [[Requirement.single_cell(Perm((0,)), (1, 1))]]
>>> til = Tiling(obstructions, requirements)
>>> print(til)
+-+-+-+
| |●| |
+-+-+-+
|\| |1|
+-+-+-+
1: Av(012)
\: Av(01)
●: point
Crossing obstructions:
012: (0, 0), (2, 0), (2, 0)
Requirement 0:
0: (1, 1)
>>> til.dimensions
(3, 2)
>>> sorted(til.active_cells)
[(0, 0), (1, 1), (2, 0)]
>>> til.point_cells
frozenset({(1, 1)})
>>> sorted(til.possibly_empty)
[(0, 0), (2, 0)]
>>> til.positive_cells
frozenset({(1, 1)})
``````

There are a number of methods available on the tiling. You can generate the gridded permutations satisfying the obtructions and requirements using the `gridded_perms_of_length` method.

``````>>> for i in range(4):
...     for gp in til.gridded_perms_of_length(i):
...         print(gp)
0: (1, 1)
10: (1, 1), (2, 0)
01: (0, 0), (1, 1)
210: (1, 1), (2, 0), (2, 0)
201: (1, 1), (2, 0), (2, 0)
120: (0, 0), (1, 1), (2, 0)
021: (0, 0), (1, 1), (2, 0)
102: (0, 0), (0, 0), (1, 1)
``````

There are numerous other methods and properties. Many of these specific to the `tilescope` algorithm, discussed in Christian Bean’s PhD thesis.