Parallelogram Polyominoes


The goal of this module is to give some tools to manipulate the parallelogram polyominoes.

class sage.combinat.parallelogram_polyomino.LocalOptions(name=u'', **options)

This class allow to add local options to an object. LocalOptions is like a dictionary, it has keys and values that represent options and the values associated to the option. This is useful to decorate an object with some optional informations.

LocalOptions should be used as follow.

INPUTS:

  • name – The name of the LocalOptions
  • <options>=dict(...) – dictionary specifying an option

The options are specified by keyword arguments with their values being a dictionary which describes the option. The allowed/expected keys in the dictionary are:

  • checker – a function for checking whether a particular value for the option is valid
  • default – the default value of the option
  • values – a dictionary of the legal values for this option (this automatically defines the corresponding checker); this dictionary gives the possible options, as keys, together with a brief description of them
sage: from sage.combinat.parallelogram_polyomino import LocalOptions
sage: o = LocalOptions(
....:     'Name Example',
....:     delim=dict(
....:         default='b',
....:         values={'b':'the option b', 'p':'the option p'}
....:     )
....: )
sage: class Ex:
....:     options=o
....:     def _repr_b(self): return "b"
....:     def _repr_p(self): return "p"
....:     def __repr__(self): return self.options._dispatch(
....:         self, '_repr_','delim'
....:     )
sage: e = Ex(); e
b
sage: e.options(delim='p'); e
p

This class is temporary, in the future, this class should be integrated in sage.structure.global_options.py. We should split global_option in two classes LocalOptions and GlobalOptions.

keys()

Return the list of the options in self.

EXAMPLES:

sage: from sage.combinat.parallelogram_polyomino import (
....:     LocalOptions
....: )
sage: o = LocalOptions(
....:     "Name Example",
....:     tikz_options=dict(
....:         default="toto",
....:         values=dict(
....:             toto="name",
....:             x="3"
....:         )
....:     ),
....:     display=dict(
....:         default="list",
....:         values=dict(
....:             list="list representation",
....:             diagram="diagram representation"
....:         )
....:     )
....: )
sage: keys=o.keys()
sage: keys.sort()
sage: keys
['display', 'tikz_options']
class sage.combinat.parallelogram_polyomino.ParallelogramPolyomino(parent, value, check=True)

Bases: sage.structure.list_clone.ClonableList

Parallelogram Polyominoes.

A parallelogram polyomino is a finite connected union of cells whose boundary can be decomposed in two paths, the upper and the lower paths, which are comprised of north and east unit steps and meet only at their starting and final points.

Parallelogram Polyominoes can be defined with those two paths.

EXAMPLES:

sage: pp = ParallelogramPolyomino([[0, 1], [1, 0]])
sage: pp
[[0, 1], [1, 0]]
area()

Return the area of the parallelogram polyomino. The area of a parallelogram polyomino is the number of cells of the parallelogram polyomino.

EXAMPLES:

sage: pp = ParallelogramPolyomino(
....:     [
....:         [0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1],
....:         [1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0]
....:     ]
....: )
sage: pp.area()
13

sage: pp = ParallelogramPolyomino([[0, 1], [1, 0]])
sage: pp.area()
1

sage: pp = ParallelogramPolyomino([[1], [1]])
sage: pp.area()
0
bounce(direction=1)

Return the bounce of the parallelogram polyomino.

Let p be the bounce path of the parallelogram polyomino (bounce_path()). The bounce is defined by:

sum([(1+ floor(i/2))*p[i] for i in range(len(p))])

INPUT:

  • direction – the initial direction of the bounce path (see bounce_path() for the definition).

EXAMPLES:

sage: PP = ParallelogramPolyomino(
....:     [[0, 0, 1, 0, 1, 1], [1, 1, 0, 0, 1, 0]]
....: )
sage: PP.bounce(direction=1)
6
sage: PP.bounce(direction=0)
7

sage: PP = ParallelogramPolyomino(
....:     [
....:         [0, 0, 1, 1, 1, 0, 0, 1, 1],
....:         [1, 1, 1, 0, 1, 1, 0, 0, 0]
....:     ]
....: )
sage: PP.bounce(direction=1)
12
sage: PP.bounce(direction=0)
10

sage: PP = ParallelogramPolyomino([[0, 1], [1, 0]])
sage: PP.bounce(direction=1)
1
sage: PP.bounce(direction=0)
1

sage: PP = ParallelogramPolyomino([[1], [1]])
sage: PP.bounce(direction=1)
0
sage: PP.bounce(direction=0)
0
bounce_path(direction=1)

Return the bounce path of the parallelogram polyomino.

The bounce path is a path with two steps (1, 0) and (0, 1).

If ‘direction’ is 1 (resp. 0), the bounce path is the path starting at position (h=1, w=0) (resp. (h=0, w=1)) with initial direction, the vector (0, 1) (resp. (1, 0)), and turning each time the path crosses the perimeter of the parallelogram polyomino.

The path is coded by a list of integers. Each integer represents the size of the path between two turnings.

You can visualize the two bounce paths by using the following commands.

INPUT:

  • direction – the initial direction of the bounce path (see above for the definition).

EXAMPLES:

sage: PP = ParallelogramPolyomino(
....:     [[0, 0, 1, 0, 1, 1], [1, 1, 0, 0, 1, 0]]
....: )
sage: PP.bounce_path(direction=1)
[2, 2, 1]
sage: PP.bounce_path(direction=0)
[2, 1, 1, 1]

sage: PP = ParallelogramPolyomino(
....:     [
....:         [0, 0, 1, 1, 1, 0, 0, 1, 1],
....:         [1, 1, 1, 0, 1, 1, 0, 0, 0]
....:     ]
....: )
sage: PP.bounce_path(direction=1)
[3, 1, 2, 2]
sage: PP.bounce_path(direction=0)
[2, 4, 2]

sage: PP = ParallelogramPolyomino(
....:     [[0, 0, 1, 0, 1, 1], [1, 1, 0, 0, 1, 0]]
....: )
sage: PP.set_options(
....:     drawing_components=dict(
....:         diagram = True
....:         , bounce_0 = True
....:         , bounce_1 = True
....:     )
....: )
sage: view(PP) # not tested

sage: PP = ParallelogramPolyomino([[0, 1], [1, 0]])
sage: PP.bounce_path(direction=1)
[1]
sage: PP.bounce_path(direction=0)
[1]

sage: PP = ParallelogramPolyomino([[1], [1]])
sage: PP.bounce_path(direction=1)
[]
sage: PP.bounce_path(direction=0)
[]
box_is_node(pos)

Return True if the box contains a node in the context of the Aval-Boussicault bijection between parallelogram polyomino and binary tree. A box is a node if there is no cell on the top of the box in the same column or on the left of the box.in the same row.

INPUT:

  • pos – the [x,y] coordinate of the box.

OUTPUT:

A boolean

EXAMPLES:

sage: pp = ParallelogramPolyomino(
....:     [[0, 0, 1, 0, 0, 0, 1, 1], [1, 1, 0, 1, 0, 0, 0, 0]]
....: )
sage: pp.set_options(display='drawing')
sage: pp
[1 1 0]
[1 1 1]
[0 1 1]
[0 1 1]
[0 1 1]
sage: pp.box_is_node([2,1])
True
sage: pp.box_is_node([2,0])
False
sage: pp.box_is_node([1,1])
False
box_is_root(box)

Return True if the box contains the root of the tree : it is the top-left box of the parallelogram polyomino.

INPUT:

  • box – the x,y coordinate of the cell.

EXAMPLES:

sage: pp = ParallelogramPolyomino(
....:     [[0, 0, 1, 0, 0, 0, 1, 1], [1, 1, 0, 1, 0, 0, 0, 0]]
....: )
sage: pp.box_is_root([0, 0])
True
sage: pp.box_is_root([0, 1])
False
cell_is_inside(w, h)

Determine whether the cell at a given position is inside the parallelogram polyomino.

INPUT:

  • w – The x coordinate of the box position.
  • h – The y coordinate of the box position.

OUTPUT:

Return 0 if there is no cell at the given position, return 1 if there is a cell.

EXAMPLES:

sage: pp = ParallelogramPolyomino(
....:     [
....:         [0, 1, 0, 0, 1, 1, 0, 1, 1, 1],
....:         [1, 1, 1, 0, 1, 0, 0, 1, 1, 0]
....:     ]
....: )
sage: pp.cell_is_inside(0, 0)
1
sage: pp.cell_is_inside(1, 0)
1
sage: pp.cell_is_inside(0, 1)
0
sage: pp.cell_is_inside(3, 0)
0
sage: pp.cell_is_inside(pp.width()-1,pp.height()-1)
1
sage: pp.cell_is_inside(pp.width(),pp.height()-1)
0
sage: pp.cell_is_inside(pp.width()-1,pp.height())
0
check()

This method raises an error if the internal data of the class does not represent a parallelogram polyomino.

EXAMPLES:

sage: pp = ParallelogramPolyomino(
....:     [
....:         [0, 0, 0, 1, 0, 1, 0, 1, 1],
....:         [1, 0, 1, 1, 0, 0, 1, 0, 0]
....:     ]
....: )
sage: pp = ParallelogramPolyomino([[0, 1], [1, 0]])
sage: pp = ParallelogramPolyomino([[1], [1]])

sage: pp = ParallelogramPolyomino(
....:     [[1, 0], [0, 1]]
....: ) # indirect doctest
Traceback (most recent call last):
...
ValueError: the lower and upper paths are crossing

sage: pp = ParallelogramPolyomino([[1], [0, 1]]) # indirect doctest
Traceback (most recent call last):
...
ValueError: the lower and upper paths have different sizes (2 != 1)

sage: pp = ParallelogramPolyomino([[1], [0]]) # indirect doctest
Traceback (most recent call last):
...
ValueError: the two paths have distinct ends

sage: pp = ParallelogramPolyomino([[0], [1]]) # indirect doctest
Traceback (most recent call last):
...
ValueError: the two paths have distinct ends

sage: pp = ParallelogramPolyomino([[0], [0]]) # indirect doctest
Traceback (most recent call last):
...
ValueError: the lower or the upper path can't be equal to [0]

sage: pp = ParallelogramPolyomino([[], [0]])  # indirect doctest
Traceback (most recent call last):
...
ValueError: the lower or the upper path can't be equal to []

sage: pp = ParallelogramPolyomino([[0], []])  # indirect doctest
Traceback (most recent call last):
...
ValueError: the lower or the upper path can't be equal to []

sage: pp = ParallelogramPolyomino([[], []])  # indirect doctest
Traceback (most recent call last):
...
ValueError: the lower or the upper path can't be equal to []
degree_convexity()

Return the degree convexity of a parallelogram polyomino.

A convex polyomino is said to be k-convex if every pair of its cells can be connected by a monotone path (path with south and east steps) with at most k changes of direction. The degree of convexity of a convex polyomino P is the smallest integer k such that P is k-convex.

If the parallelogram polyomino is empty, the function return -1.

EXAMPLES:

sage: pp = ParallelogramPolyomino(
....:     [
....:         [0, 0, 0, 1, 0, 1, 0, 1, 1],
....:         [1, 0, 1, 1, 0, 0, 1, 0, 0]
....:     ]
....: )
sage: pp.degree_convexity()
3

sage: pp = ParallelogramPolyomino([[0, 1], [1, 0]])
sage: pp.degree_convexity()
0

sage: pp = ParallelogramPolyomino([[1], [1]])
sage: pp.degree_convexity()
-1
static from_dyck_word(dyck, bijection=None)

Convert a Dyck word to parallelogram polyomino.

INPUT:

  • dyck – a Dyck word
  • bijection – string or None (default:None) the bijection to use. See to_dyck_word() for more details.

OUTPUT:

A parallelogram polyomino.

EXAMPLES:

sage: dyck = DyckWord([1, 1, 0, 1, 1, 0, 1, 0, 0, 0])
sage: pp = ParallelogramPolyomino.from_dyck_word(dyck)
sage: pp
[[0, 1, 0, 0, 1, 1], [1, 1, 1, 0, 0, 0]]
sage: pp = ParallelogramPolyomino.from_dyck_word(
....:     dyck, bijection='Delest-Viennot'
....: )
sage: pp
[[0, 1, 0, 0, 1, 1], [1, 1, 1, 0, 0, 0]]
geometry()

Return a pair [h, w] containing the height and the width of the parallelogram polyomino.

EXAMPLES:

sage: pp = ParallelogramPolyomino(
....:     [[0, 1, 1, 1, 1], [1, 1, 1, 1, 0]]
....: )
sage: pp.geometry()
[1, 4]

sage: pp = ParallelogramPolyomino([[0, 1], [1, 0]])
sage: pp.geometry()
[1, 1]

sage: pp = ParallelogramPolyomino([[1], [1]])
sage: pp.geometry()
[0, 1]
get_BS_nodes()

Return the list of cells containing node of the left and right planar tree in the Boussicault-Socci bijection.

EXAMPLES:

sage: pp = ParallelogramPolyomino(
....:     [[0, 0, 1, 0, 0, 0, 1, 1], [1, 1, 0, 1, 0, 0, 0, 0]]
....: )
sage: pp.set_options(display='drawing')
sage: pp
[1 1 0]
[1 1 1]
[0 1 1]
[0 1 1]
[0 1 1]
sage: sorted(pp.get_BS_nodes())
[[0, 1], [1, 0], [1, 2], [2, 1], [3, 1], [4, 1]]

You can draw the point inside the parallelogram polyomino by typing (the left nodes are in blue, and the right node are in red)

sage: pp.set_options(drawing_components=dict(tree=True))
sage: view(pp) # not tested
get_array()

Return an array of 0s and 1s such that the 1s represent the boxes of the parallelogram polyomino.

EXAMPLES:

sage: pp = ParallelogramPolyomino(
....:     [
....:         [0, 0, 0, 0, 1, 0, 1, 0, 1],
....:         [1, 0, 0, 0, 1, 1, 0, 0, 0]
....:     ]
....: )
sage: matrix(pp.get_array())
[1 0 0]
[1 0 0]
[1 0 0]
[1 1 1]
[0 1 1]
[0 0 1]

sage: pp = ParallelogramPolyomino([[0, 1], [1, 0]])
sage: pp.get_array()
[[1]]

sage: pp = ParallelogramPolyomino([[1], [1]])
sage: pp.get_array()
[]
get_left_BS_nodes()

Return the list of cells containing node of the left planar tree in the Boussicault-Socci bijection between parallelogram polyominoes and pair of ordered trees.

OUTPUT:

A list of [row,colum] position of cells.

EXAMPLES:

sage: pp = ParallelogramPolyomino(
....:     [[0, 0, 1, 0, 0, 0, 1, 1], [1, 1, 0, 1, 0, 0, 0, 0]]
....: )
sage: pp.set_options(display='drawing')
sage: pp
[1 1 0]
[1 1 1]
[0 1 1]
[0 1 1]
[0 1 1]
sage: sorted(pp.get_left_BS_nodes())
[[0, 1], [2, 1], [3, 1], [4, 1]]

sage: pp = ParallelogramPolyomino(
....:     [[0, 0, 1, 0, 0, 0, 1, 1], [1, 0, 1, 1, 0, 0, 0, 0]]
....: )
sage: pp.set_options(display='drawing')
sage: pp
[1 0 0]
[1 1 1]
[0 1 1]
[0 1 1]
[0 1 1]
sage: sorted(pp.get_left_BS_nodes())
[]

You can draw the point inside the parallelogram polyomino by typing (the left nodes are in blue, and the right node are in red)

sage: pp.set_options(drawing_components=dict(tree=True))
sage: view(pp) # not tested
get_node_position_from_box(box_position, direction, nb_crossed_nodes=[0])

This function starts from a cell inside a parallelogram polyomino and a direction.

If direction is equal to 0, the function selects the column associated with the y-coordinate of box_position and then returns the topmost cell of the column that is on the top of box_position (the cell of box_position is included).

If direction is equal to 1, the function selects the row associated with the x-coordinate of box_position and then returns the leftmost cell of the row that is on the left of box_position. (the cell of box_position is included).

This function updates the entry of nb_crossed_nodes. The function increases the entry of nb_crossed_nodes by the number of boxes that is a node (see box_is_node) located on the top if direction is 0 (resp. on the left if direction is 1) of box_position (cell at box_position is excluded).

INPUT:

  • box_position – the position of the statring cell.
  • direction – the direction (0 or 1).
  • nb_crossed_nodes[0] (default) a list containg just one integer.

OUTPUT:

A [row,colum] position of the cell.

EXAMPLES:

sage: pp = ParallelogramPolyomino(
....:     [[0, 0, 1, 0, 0, 0, 1, 1], [1, 0, 1, 1, 0, 0, 0, 0]]
....: )
sage: matrix(pp.get_array())
[1 0 0]
[1 1 1]
[0 1 1]
[0 1 1]
[0 1 1]
sage: l = [0]
sage: pp.get_node_position_from_box([3, 2], 0, l)
[1, 2]
sage: l
[1]
sage: l = [0]
sage: pp.get_node_position_from_box([3, 2], 1, l)
[3, 1]
sage: l
[1]
sage: l = [0]
sage: pp.get_node_position_from_box([1, 2], 0, l)
[1, 2]
sage: l
[0]
sage: l = [0]
sage: pp.get_node_position_from_box([1, 2], 1, l)
[1, 0]
sage: l
[2]
sage: l = [0]
sage: pp.get_node_position_from_box([3, 1], 0, l)
[1, 1]
sage: l
[2]
sage: l = [0]
sage: pp.get_node_position_from_box([3, 1], 1, l)
[3, 1]
sage: l
[0]
get_options()

Return all the options of the object.

EXAMPLES:

sage: pp = ParallelogramPolyomino([[0, 1], [1, 0]])
sage: pp.get_options()
Current options for ParallelogramPolyominoes_size
  - display:            u'list'
  - drawing_components: {'bounce_0': False, 'bounce_1': False, 'diagram': True, 'tree': False}
  - latex:              u'drawing'
  - tikz_options:       {'color_bounce_0': u'red',
    'color_bounce_1': u'blue', 'color_line': u'black', 'color_point': u'black',
    'line_size': 1, 'mirror': None, 'point_size': 3.5,
    'rotation': 0, 'scale': 1, 'translation': [0, 0]}
get_right_BS_nodes()

Return the list of cells containing node of the right planar tree in the Boussicault-Socci bijection between parallelogram polyominoes and pair of ordered trees.

EXAMPLES:

sage: pp = ParallelogramPolyomino(
....:     [[0, 0, 1, 0, 0, 0, 1, 1], [1, 1, 0, 1, 0, 0, 0, 0]]
....: )
sage: pp.set_options(display='drawing')
sage: pp
[1 1 0]
[1 1 1]
[0 1 1]
[0 1 1]
[0 1 1]
sage: sorted(pp.get_right_BS_nodes())
[[1, 0], [1, 2]]

sage: pp = ParallelogramPolyomino(
....:     [[0, 0, 1, 0, 0, 0, 1, 1], [1, 0, 1, 1, 0, 0, 0, 0]]
....: )
sage: pp.set_options(display='drawing')
sage: pp
[1 0 0]
[1 1 1]
[0 1 1]
[0 1 1]
[0 1 1]
sage: sorted(pp.get_right_BS_nodes())
[[1, 0], [1, 1], [1, 2], [2, 1], [3, 1], [4, 1]]

You can draw the point inside the parallelogram polyomino by typing, (the left nodes are in blue, and the right node are in red)

sage: pp.set_options(drawing_components=dict(tree=True))
sage: view(pp) # not tested
get_tikz_options()

Return all the tikz options permitting to draw the parallelogram polyomino.

See LocalOption to have more informations about the modification of those options.

EXAMPLES:

sage: pp = ParallelogramPolyomino([[0, 1], [1, 0]])
sage: pp.get_tikz_options()
{'color_bounce_0': u'red',
 'color_bounce_1': u'blue',
 'color_line': u'black',
 'color_point': u'black',
 'line_size': 1,
 'mirror': None,
 'point_size': 3.5,
 'rotation': 0,
 'scale': 1,
 'translation': [0, 0]}
height()

Return the height of the parallelogram polyomino.

EXAMPLES:

sage: pp = ParallelogramPolyomino(
....:     [
....:         [0, 1, 0, 0, 1, 1, 0, 1, 1, 1],
....:         [1, 1, 1, 0, 1, 0, 0, 1, 1, 0]
....:     ]
....: )
sage: pp.height()
4

sage: pp = ParallelogramPolyomino([[0, 1], [1, 0]])
sage: pp.height()
1

sage: pp = ParallelogramPolyomino([[1], [1]])
sage: pp.height()
0
heights()

Return a list of heights of the parallelogram polyomino.

Namely, the parallelogram polyomino is split column by column and the method returns the list containing the sizes of the columns.

EXAMPLES:

sage: pp = ParallelogramPolyomino(
....:     [
....:         [0, 0, 0, 1, 0, 1, 0, 1, 1],
....:         [1, 0, 1, 1, 0, 0, 1, 0, 0]
....:     ]
....: )
sage: pp.heights()
[3, 3, 4, 2]

sage: pp = ParallelogramPolyomino([[0, 1], [1, 0]])
sage: pp.heights()
[1]

sage: pp = ParallelogramPolyomino([[1], [1]])
sage: pp.heights()
[0]
is_flat()

Return whether the two bounce paths join together in the rightmost cell of the bottom row of P.

EXAMPLES:

sage: pp = ParallelogramPolyomino(
....:     [
....:         [0, 0, 0, 1, 0, 1, 0, 1, 1],
....:         [1, 0, 1, 1, 0, 0, 1, 0, 0]
....:     ]
....: )
sage: pp.is_flat()
False

sage: pp = ParallelogramPolyomino([[0, 1], [1, 0]])
sage: pp.is_flat()
True

sage: pp = ParallelogramPolyomino([[1], [1]])
sage: pp.is_flat()
True
is_k_directed(k)

Return whether the Polyomino Parallelogram is k-directed.

A convex polyomino is said to be k-convex if every pair of its cells can be connected by a monotone path (path with south and east steps) with at most k changes of direction.

The degree of convexity of a convex polyomino P is the smallest integer k such that P is k-convex.

INPUT:

  • k – An non negative integer.

EXAMPLES:

sage: pp = ParallelogramPolyomino(
....:     [
....:         [0, 0, 0, 1, 0, 1, 0, 1, 1],
....:         [1, 0, 1, 1, 0, 0, 1, 0, 0]
....:     ]
....: )
sage: pp.is_k_directed(3)
True
sage: pp.is_k_directed(4)
True
sage: pp.is_k_directed(5)
True
sage: pp.is_k_directed(0)
False
sage: pp.is_k_directed(1)
False
sage: pp.is_k_directed(2)
False

sage: pp = ParallelogramPolyomino([[0, 1], [1, 0]])
sage: pp.is_k_directed(0)
True
sage: pp.is_k_directed(1)
True

sage: pp = ParallelogramPolyomino([[1], [1]])
sage: pp.is_k_directed(0)
True
sage: pp.is_k_directed(1)
True
lower_heights()

Return the list of heights associated to each vertical step of the parallogram polyomino’s lower path.

OUTPUT:

A list of integers.

EXAMPLES:

sage: ParallelogramPolyomino([[0, 1], [1, 0]]).lower_heights()
[1]
sage: ParallelogramPolyomino(
....:     [[0, 0, 1, 1, 0, 1, 1, 1], [1, 0, 1, 1, 0, 1, 1, 0]]
....: ).lower_heights()
[2, 2, 3, 3, 3]
lower_path()

Get the lower path of the parallelogram polyomino.

EXAMPLES:

sage: lower_path = [0, 0, 1, 0, 1, 1]
sage: upper_path = [1, 1, 0, 1, 0, 0]
sage: pp = ParallelogramPolyomino([lower_path, upper_path])
sage: pp.lower_path()
[0, 0, 1, 0, 1, 1]
lower_widths()

Return the list of widths associated to each horizontal step of the parallogram polyomino’s lower path.

OUTPUT:

A list of integers.

EXAMPLES:

sage: ParallelogramPolyomino([[0, 1], [1, 0]]).lower_widths()
[0]
sage: ParallelogramPolyomino(
....:     [[0, 0, 1, 1, 0, 1, 1, 1], [1, 0, 1, 1, 0, 1, 1, 0]]
....: ).lower_widths()
[0, 0, 2]
set_options(*get_value, **set_value)

Set new options to the object. See LocalOptions for more info.

EXAMPLES:

sage: pp = ParallelogramPolyomino(
....:     [
....:         [0, 0, 0, 0, 1, 0, 1, 0, 1],
....:         [1, 0, 0, 0, 1, 1, 0, 0, 0]
....:     ]
....: )
sage: pp
[[0, 0, 0, 0, 1, 0, 1, 0, 1], [1, 0, 0, 0, 1, 1, 0, 0, 0]]
sage: pp.set_options(display='drawing')
sage: pp
[1 0 0]
[1 0 0]
[1 0 0]
[1 1 1]
[0 1 1]
[0 0 1]

sage: pp = ParallelogramPolyomino([[0, 1], [1, 0]])
sage: view(PP) # not tested
sage: pp.set_options(
....:     drawing_components=dict(
....:         diagram = True,
....:         bounce_0 = True,
....:         bounce_1 = True,
....:     )
....: )
sage: view(PP) # not tested
size()

Return the size of the parallelogram polyomino.

The size of a parallelogram polyomino is its half-perimeter.

EXAMPLES:

sage: pp = ParallelogramPolyomino(
....:     [[0, 0, 0, 0, 1, 0, 1, 1], [1, 0, 0, 0, 1, 1, 0, 0]]
....: )
sage: pp.size()
8

sage: pp = ParallelogramPolyomino([[0, 1], [1, 0]])
sage: pp.size()
2

sage: pp = ParallelogramPolyomino([[1], [1]])
sage: pp.size()
1
to_binary_tree(bijection=None)

Convert to a binary tree

INPUT:

  • bijection – string or None (default:None) The name of bijection to use for the conversion. The possible values are None or 'Aval-Boussicault'. The None value is equivalent to 'Aval-Boussicault'.

EXAMPLES:

sage: pp = ParallelogramPolyomino(
....:     [
....:         [0, 0, 1, 0, 1, 0, 1, 0, 1, 1],
....:         [1, 1, 0, 1, 1, 0, 0, 0, 1, 0]
....:     ]
....: )
sage: pp.to_binary_tree()
[[., [[., .], [[., [., .]], .]]], [[., .], .]]

sage: pp = ParallelogramPolyomino([[0, 1], [1, 0]])
sage: pp.to_binary_tree()
[., .]

sage: pp = ParallelogramPolyomino([[1], [1]])
sage: pp.to_binary_tree()
.
to_dyck_word(bijection=None)

Convert to a Dyck word.

This bijection is described page 179 and page 180 Figure 6 in the article [DeVi1984].

INPUT:

  • bijection – string or None (default:None) The name of the bijection. If it is set to None then the 'Delest-Viennot' bijection is used. Expected values are None or 'Delest-Viennot'.

OUTPUT:

a Dyck word

EXAMPLES:

sage: pp = ParallelogramPolyomino(
....:     [[0, 1, 0, 0, 1, 1], [1, 1, 1, 0, 0, 0]]
....: )
sage: pp.to_dyck_word()
[1, 1, 0, 1, 1, 0, 1, 0, 0, 0]
sage: pp.to_dyck_word(bijection='Delest-Viennot')
[1, 1, 0, 1, 1, 0, 1, 0, 0, 0]
to_ordered_tree(bijection=None)

Return an ordered tree from the parallelogram polyomino.

Different bijections can be specified.

The bijection ‘via dyck and Delest-Viennot’ is the composition of _to_dyck_delest_viennot() and the classical bijection between dyck paths and ordered trees.

The bijection between Dyck Word and ordered trees is described in [DerZak1980] (See page 12 and 13 and Figure 3.1).

The bijection ‘Boussicault-Socci’ is described in [BRS2015].

INPUT:

  • bijection – string or None (default:None) The name of bijection to use for the conversion. The possible value are None, 'Boussicault-Socci' or 'via dyck and Delest-Viennot'. The None value is equivalent to the 'Boussicault-Socci' value.

EXAMPLES:

sage: pp = ParallelogramPolyomino(
....:     [
....:         [0, 0, 1, 0, 1, 0, 1, 0, 1, 1],
....:         [1, 1, 0, 1, 1, 0, 0, 0, 1, 0]
....:     ]
....: )
sage: pp.to_ordered_tree()
[[[[[]], [[[]]]]], [[]]]

sage: pp = ParallelogramPolyomino([[0, 1], [1, 0]])
sage: pp.to_ordered_tree()
[[]]

sage: pp = ParallelogramPolyomino([[1], [1]])
sage: pp.to_ordered_tree()
[]

sage: pp = ParallelogramPolyomino(
....:     [
....:         [0, 0, 1, 0, 1, 0, 1, 0, 1, 1],
....:         [1, 1, 0, 1, 1, 0, 0, 0, 1, 0]
....:     ]
....: )
sage: pp.to_ordered_tree('via dyck and Delest-Viennot')
[[[[]], [[[]], []]], [[]]]
to_tikz()

Return the tikz code of the parallelogram polyomino.

This code is the code present inside a tikz latex environment.

We can modify the output with the options.

EXAMPLES:

sage: pp = ParallelogramPolyomino(
....:     [[0,0,0,1,1,0,1,0,0,1,1,1],[1,1,1,0,0,1,1,0,0,1,0,0]]
....: )
sage: print(pp.to_tikz())

  \draw[color=black, line width=1] (0.000000, 6.000000) --
(0.000000, 3.000000);
  \draw[color=black, line width=1] (6.000000, 2.000000) --
(6.000000, 0.000000);
  \draw[color=black, line width=1] (0.000000, 6.000000) --
(3.000000, 6.000000);
  \draw[color=black, line width=1] (3.000000, 0.000000) --
(6.000000, 0.000000);
  \draw[color=black, line width=1] (1.000000, 6.000000) --
(1.000000, 3.000000);
  \draw[color=black, line width=1] (2.000000, 6.000000) --
(2.000000, 2.000000);
  \draw[color=black, line width=1] (3.000000, 6.000000) --
(3.000000, 0.000000);
  \draw[color=black, line width=1] (4.000000, 4.000000) --
(4.000000, 0.000000);
  \draw[color=black, line width=1] (5.000000, 4.000000) --
(5.000000, 0.000000);
  \draw[color=black, line width=1] (0.000000, 5.000000) --
(3.000000, 5.000000);
  \draw[color=black, line width=1] (0.000000, 4.000000) --
(5.000000, 4.000000);
  \draw[color=black, line width=1] (0.000000, 3.000000) --
(5.000000, 3.000000);
  \draw[color=black, line width=1] (2.000000, 2.000000) --
(6.000000, 2.000000);
  \draw[color=black, line width=1] (3.000000, 1.000000) --
(6.000000, 1.000000);
sage: pp.set_options(
....:     drawing_components=dict(
....:         diagram=True,
....:         tree=True,
....:         bounce_0=True,
....:         bounce_1=True
....:     )
....: )
sage: print(pp.to_tikz())

  \draw[color=black, line width=1] (0.000000, 6.000000) --
(0.000000, 3.000000);
  \draw[color=black, line width=1] (6.000000, 2.000000) --
(6.000000, 0.000000);
  \draw[color=black, line width=1] (0.000000, 6.000000) --
(3.000000, 6.000000);
  \draw[color=black, line width=1] (3.000000, 0.000000) --
(6.000000, 0.000000);
  \draw[color=black, line width=1] (1.000000, 6.000000) --
(1.000000, 3.000000);
  \draw[color=black, line width=1] (2.000000, 6.000000) --
(2.000000, 2.000000);
  \draw[color=black, line width=1] (3.000000, 6.000000) --
(3.000000, 0.000000);
  \draw[color=black, line width=1] (4.000000, 4.000000) --
(4.000000, 0.000000);
  \draw[color=black, line width=1] (5.000000, 4.000000) --
(5.000000, 0.000000);
  \draw[color=black, line width=1] (0.000000, 5.000000) --
(3.000000, 5.000000);
  \draw[color=black, line width=1] (0.000000, 4.000000) --
(5.000000, 4.000000);
  \draw[color=black, line width=1] (0.000000, 3.000000) --
(5.000000, 3.000000);
  \draw[color=black, line width=1] (2.000000, 2.000000) --
(6.000000, 2.000000);
  \draw[color=black, line width=1] (3.000000, 1.000000) --
(6.000000, 1.000000);
  \draw[color=blue, line width=3] (0.000000, 5.000000) --
(3.000000, 5.000000);
  \draw[color=blue, line width=3] (3.000000, 5.000000) --
(3.000000, 2.000000);
  \draw[color=blue, line width=3] (3.000000, 2.000000) --
(5.000000, 2.000000);
  \draw[color=blue, line width=3] (5.000000, 2.000000) --
(5.000000, 0.000000);
  \draw[color=blue, line width=3] (5.000000, 0.000000) --
(6.000000, 0.000000);
  \draw[color=red, line width=2] (1.000000, 6.000000) --
(1.000000, 3.000000);
  \draw[color=red, line width=2] (1.000000, 3.000000) --
(5.000000, 3.000000);
  \draw[color=red, line width=2] (5.000000, 3.000000) --
(5.000000, 0.000000);
  \draw[color=red, line width=2] (5.000000, 0.000000) --
(6.000000, 0.000000);
  \filldraw[color=black] (0.500000, 4.500000) circle (3.5pt);
  \filldraw[color=black] (0.500000, 3.500000) circle (3.5pt);
  \filldraw[color=black] (2.500000, 2.500000) circle (3.5pt);
  \filldraw[color=black] (3.500000, 1.500000) circle (3.5pt);
  \filldraw[color=black] (3.500000, 0.500000) circle (3.5pt);
  \filldraw[color=black] (1.500000, 5.500000) circle (3.5pt);
  \filldraw[color=black] (2.500000, 5.500000) circle (3.5pt);
  \filldraw[color=black] (3.500000, 3.500000) circle (3.5pt);
  \filldraw[color=black] (4.500000, 3.500000) circle (3.5pt);
  \filldraw[color=black] (5.500000, 1.500000) circle (3.5pt);
  \filldraw[color=black] (0.500000, 5.500000) circle (3.5pt);
upper_heights()

Return the list of heights associated to each vertical step of the parallogram polyomino’s upper path.

OUTPUT:

A list of integers.

EXAMPLES:

sage: ParallelogramPolyomino([[0, 1], [1, 0]]).upper_heights()
[0]
sage: ParallelogramPolyomino(
....:     [[0, 0, 1, 1, 0, 1, 1, 1], [1, 0, 1, 1, 0, 1, 1, 0]]
....: ).upper_heights()
[0, 1, 1, 2, 2]
upper_path()

Get the upper path of the parallelogram polyomino.

EXAMPLES:

sage: lower_path = [0, 0, 1, 0, 1, 1]
sage: upper_path = [1, 1, 0, 1, 0, 0]
sage: pp = ParallelogramPolyomino([lower_path, upper_path])
sage: pp.upper_path()
[1, 1, 0, 1, 0, 0]
upper_widths()

Return the list of widths associated to each horizontal step of the parallogram polyomino’s upper path.

OUTPUT:

A list of integers.

EXAMPLES:

sage: ParallelogramPolyomino([[0, 1], [1, 0]]).upper_widths()
[1]
sage: ParallelogramPolyomino(
....:     [[0, 0, 1, 1, 0, 1, 1, 1], [1, 0, 1, 1, 0, 1, 1, 0]]
....: ).upper_widths()
[1, 3, 5]
width()

Return the width of the parallelogram polyomino.

EXAMPLES:

sage: pp = ParallelogramPolyomino(
....:     [
....:         [0, 1, 0, 0, 1, 1, 0, 1, 1, 1],
....:         [1, 1, 1, 0, 1, 0, 0, 1, 1, 0]
....:     ]
....: )
sage: pp.width()
6

sage: pp = ParallelogramPolyomino([[0, 1], [1, 0]])
sage: pp.width()
1

sage: pp = ParallelogramPolyomino([[1], [1]])
sage: pp.width()
1
widths()

Return a list of the widths of the parallelogram polyomino.

Namely, the parallelogram polyomino is split row by row and the method returns the list containing the sizes of the rows.

EXAMPLES:

sage: pp = ParallelogramPolyomino(
....:     [
....:         [0, 0, 0, 1, 0, 1, 0, 1, 1],
....:         [1, 0, 1, 1, 0, 0, 1, 0, 0]
....:     ]
....: )
sage: pp.widths()
[1, 3, 3, 3, 2]

sage: pp = ParallelogramPolyomino([[0, 1], [1, 0]])
sage: pp.widths()
[1]

sage: pp = ParallelogramPolyomino([[1], [1]])
sage: pp.widths()
[]
sage.combinat.parallelogram_polyomino.ParallelogramPolyominoes = Factory for parallelogram polyominoes
class sage.combinat.parallelogram_polyomino.ParallelogramPolyominoesFactory

Bases: sage.structure.set_factories.SetFactory

The parallelogram polyominoes factory.

EXAMPLES:

sage: PPS = ParallelogramPolyominoes(size=4)
sage: PPS
Parallelogram polyominoes of size 4

sage: sorted(list(PPS))
[[[0, 0, 0, 1], [1, 0, 0, 0]],
 [[0, 0, 1, 1], [1, 0, 1, 0]],
 [[0, 0, 1, 1], [1, 1, 0, 0]],
 [[0, 1, 0, 1], [1, 1, 0, 0]],
 [[0, 1, 1, 1], [1, 1, 1, 0]]]

sage: PPS = ParallelogramPolyominoes()
sage: PPS
Parallelogram polyominoes
sage: PPS.cardinality()
+Infinity
sage.combinat.parallelogram_polyomino.ParallelogramPolyominoesOptions = Current options for ParallelogramPolyominoes_size - display: u'list' - drawing_components: {'bounce_0': False, 'bounce_1': False, 'diagram': True, 'tree': False} - latex: u'drawing' - tikz_options: {'color_bounce_0': u'red', 'color_bounce_1': u'blue', 'color_line': u'black', 'color_point': u'black', 'line_size': 1, 'mirror': None, 'point_size': 3.5, 'rotation': 0, 'scale': 1, 'translation': [0, 0]}

This global option contains all the data needed by the Parallelogram classes to draw, display in ASCII, compile in latex a parallelogram polyomino.

The options avalaible are :

  • tikz_options : this option configurate all the information useful to generate TIKZ code. For example, color, line size, etc …
  • drawing_components : this option is used to explain to the system which component of the drawing you want to draw. For example, you can ask to draw some elements of the following list : - the diagram, - the tree inside the parallelogram polyomino, - the bounce paths inside the parallelogram polyomino.
  • display : this option is used to configurate the ASCII display. the option avalaible are : - list : (this is the default value) is used to represent PP as a list containinge the upper and lower path. - drawing : this value is used to explain we want to display an array with the PP drawn inside (with connected 1).
  • latex : Same as display. The default is “drawing”.

See ParallelogramPolyomino.get_options() for more details and for an user use of options.

EXAMPLES:

sage: from sage.combinat.parallelogram_polyomino import (
....:     ParallelogramPolyominoesOptions
....: )
sage: opt = ParallelogramPolyominoesOptions['tikz_options']
sage: opt
{'color_bounce_0': u'red',
 'color_bounce_1': u'blue',
 'color_line': u'black',
 'color_point': u'black',
 'line_size': 1,
 'mirror': None,
 'point_size': 3.5,
 'rotation': 0,
 'scale': 1,
 'translation': [0, 0]}
class sage.combinat.parallelogram_polyomino.ParallelogramPolyominoes_all(policy)

Bases: sage.structure.set_factories.ParentWithSetFactory, sage.sets.disjoint_union_enumerated_sets.DisjointUnionEnumeratedSets

This class enumerates all the parallelogram polyominoes.

EXAMPLES:

sage: PPS = ParallelogramPolyominoes()
sage: PPS
Parallelogram polyominoes
check_element(el, check)

Check is a given element \(el\) is in the set of parallelogram polyominoes.

EXAMPLES:

sage: PPS = ParallelogramPolyominoes()
sage: ParallelogramPolyomino(
....:     [[0, 1, 1], [1, 1, 0]]
....: ) in PPS # indirect doctest
True
get_options()

Return all the options associated with the set of parallelogram polyominoes.

EXAMPLES:

sage: PPS = ParallelogramPolyominoes()
sage: options = PPS.get_options()
sage: options
Current options for ParallelogramPolyominoes_size
  - display:            u'list'
...
options = Current options for ParallelogramPolyominoes_size - display: u'list' - drawing_components: {'bounce_0': False, 'bounce_1': False, 'diagram': True, 'tree': False} - latex: u'drawing' - tikz_options: {'color_bounce_0': u'red', 'color_bounce_1': u'blue', 'color_line': u'black', 'color_point': u'black', 'line_size': 1, 'mirror': None, 'point_size': 3.5, 'rotation': 0, 'scale': 1, 'translation': [0, 0]}

The options for ParallelogramPolyominoes.

set_options(*get_value, **set_value)

Set new options to the object.

EXAMPLES:

sage: PPS = ParallelogramPolyominoes()
sage: PPS.set_options(
....:     drawing_components=dict(
....:         diagram = True,
....:         bounce_0 = True,
....:         bounce_1 = True,
....:     )
....: )
sage: pp = next(iter(PPS))
sage: view(pp) # not tested
class sage.combinat.parallelogram_polyomino.ParallelogramPolyominoes_size(size, policy)

Bases: sage.structure.set_factories.ParentWithSetFactory, sage.structure.unique_representation.UniqueRepresentation

The parallelogram polyominoes of size \(n\).

EXAMPLES:

sage: PPS = ParallelogramPolyominoes(4)
sage: PPS
Parallelogram polyominoes of size 4
sage: sorted(list(PPS))
[[[0, 0, 0, 1], [1, 0, 0, 0]],
 [[0, 0, 1, 1], [1, 0, 1, 0]],
 [[0, 0, 1, 1], [1, 1, 0, 0]],
 [[0, 1, 0, 1], [1, 1, 0, 0]],
 [[0, 1, 1, 1], [1, 1, 1, 0]]]
an_element()

Return an element of a parallelogram polyomino of a given size.

EXAMPLES:

sage: PPS = ParallelogramPolyominoes(4)
sage: PPS.an_element() in PPS
True
cardinality()

Return the number of parallelogram polyominoes.

The number of parallelogram polyominoes of size n is given by the Catalan number \(c_{n-1}\).

EXAMPLES:

sage: ParallelogramPolyominoes(1).cardinality()
1
sage: ParallelogramPolyominoes(2).cardinality()
1
sage: ParallelogramPolyominoes(3).cardinality()
2
sage: ParallelogramPolyominoes(4).cardinality()
5

sage: all(
....:     ParallelogramPolyominoes(i).cardinality()
....:     == len(list(ParallelogramPolyominoes(i)))
....:     for i in range(1,7)
....: )
True
check_element(el, check)

Check is a given element \(el\) is in the set of parallelogram polyominoes of a fixed size.

EXAMPLES:

sage: PPS = ParallelogramPolyominoes(3)
sage: ParallelogramPolyomino(
....:     [[0, 1, 1], [1, 1, 0]]
....: ) in PPS # indirect doctest
True
get_options()

Return all the options associated with all the elements of the set of parallelogram polyominoes with a fixed size.

EXAMPLES:

sage: pps = ParallelogramPolyominoes(5)
sage: pps.get_options()
Current options for ParallelogramPolyominoes_size
  - display:            u'list'
...
options = Current options for ParallelogramPolyominoes_size - display: u'list' - drawing_components: {'bounce_0': False, 'bounce_1': False, 'diagram': True, 'tree': False} - latex: u'drawing' - tikz_options: {'color_bounce_0': u'red', 'color_bounce_1': u'blue', 'color_line': u'black', 'color_point': u'black', 'line_size': 1, 'mirror': None, 'point_size': 3.5, 'rotation': 0, 'scale': 1, 'translation': [0, 0]}

The options for ParallelogramPolyominoes.

set_options(*get_value, **set_value)

Set new options to the object.

EXAMPLES:

sage: PPS = ParallelogramPolyominoes(3)
sage: PPS.set_options(
....:     drawing_components=dict(
....:         diagram = True,
....:         bounce_0 = True,
....:         bounce_1 = True,
....:     )
....: )
sage: pp = PPS[0]
sage: view(pp) # not tested
size()

Return the size of the parallelogram polyominoes generated by this parent.

EXAMPLES:

sage: ParallelogramPolyominoes(0).size()
0
sage: ParallelogramPolyominoes(1).size()
1
sage: ParallelogramPolyominoes(5).size()
5
sage.combinat.parallelogram_polyomino.default_tikz_options = {'color_bounce_0': u'red', 'color_bounce_1': u'blue', 'color_line': u'black', 'color_point': u'black', 'line_size': 1, 'mirror': None, 'point_size': 3.5, 'rotation': 0, 'scale': 1, 'translation': [0, 0]}

This is the default TIKZ options.

This option is used to configurate element of a drawing to allow TIKZ code generation.