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)
(1, 1)
(1, 1), (2, 0)
(0, 0), (1, 1)
(1, 1), (2, 0), (2, 0)
(1, 1), (2, 0), (2, 0)
(0, 0), (1, 1), (2, 0)
(0, 0), (1, 1), (2, 0)
(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.