# 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)))
>>> gp.contradictory()
False
>>> gp = GriddedPerm(Perm((0, 1, 2)), ((0, 0), (0, 1), (0, 0)))
>>> gp.contradictory()
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.