On the Generation of L-Convex Polyominoes
Paolo Massazza ∗ paolo.massazza@uninsubria.it
Abstract
We present a simple but efficient method for generating the set LPol(n) of L-convex polyominoes of size n. We show a bijection between LPol(n) and a suitable set of pairs of integer sequences. This lets us design a CAT (Constant Amortized Time) algorithm for generating LPol(n) using O( √
n) space.
1 Introduction
A polyomino P is a finite connected set of edge-to-edge adjacent square unit cells in the cartesian two-dimensional plane, defined up to translations. Several classes of polyominoes have been considered and extensively studied in enumer- ative [4, 12] or bijective combinatorics [3, 11, 18]. They have been studied in two-dimensional language theory and image treatment [8, 9], in particular from the point of view of the problem of reconstruction of P from partial informations [1, 14]. They have also deserved a particular attention in tiling theory, where they describe tile shapes [13, 17].
Here we are interested in the class of L-convex polyominoes, introduced in [7] and later studied from a combinatorial point of view in [5, 6], where the authors enumerate them with respect to the semi-perimeter and to the area.
In particular, we study the problem of designing an efficient algorithm for the exhaustive generation of L-convex polyominoes of a given size n.
We recall that a CAT (constant amortized time) algorithm for the exhaustive generation of parallelogram polyominoes of size n has been recently proposed in [15], where it is shown how to exploit a bijection between the set of parallelo- gram polyominoes of size n and a set of suitable pairs of integer partitions. By adopting a similar approach, we provide a bijection between L-convex polyomi- noes and a suitable set of integer sequences, and we show that such a bijection directly leads to a CAT algorithm for generating the set of all L-convex poly- ominoes of size n.
2 Preliminaries
A polyomino P is called convex if the intersection of P with an infinite row or column of connected cells is always connected. We indicate by CPol(n) the set
∗
Universit` a degli Studi dell’Insubria, Dipartimento di Scienze Teoriche e Applicate - Sezione
Informatica, Via Mazzini 5, 21100 Varese, Italy
of convex polyominoes of size n. The size of P is the number of its cells, s(P ).
The height and the width of P , denoted by h(P ) and w(P ), respectively, are the height and the width of the minimal rectangle which bounds P , that is,
h(P ) = max{|j 1 − j 2 | : ∃i 1 , i 2 , (i 1 , j 1 ), (i 2 , j 2 ) ∈ P } + 1, w(P ) = max{|i 1 − i 2 | : ∃j 1 , j 2 , (i 1 , j 1 ), (i 2 , j 2 ) ∈ P } + 1.
A path in P is a sequence c 1 , c 2 , . . . , c k of cells of P such that for all i, with 1 ≤ i < k, c i shares one edge with c i+1 . Convex polyominoes can be classified according to the number of vertices they share with minimal bounding rectan- gles. In particular, P can be a Ferrer diagram if it shares three vertices with the minimal bounding rectangle, while it is a stack polyomino if it shares at least two adjacent vertices. A rectangular polyomino or rectangle is a convex polyomino of height x, width y and size xy.
Ferrer diagrams of size n can be represented as integer partitions of n. An integer partition of n (also called linear partition) is a non-increasing sequence of nonnegative integers with sum n. We indicate by LP(n) the set of integer partitions of n. For any two integers x, p with p > 0, we denote by x [p] the sequence (x, . . . , x
| {z }
p
) and by · the catenation product of sequences. The length of t = (t 1 , . . . , t l ) ∈ LP(n) is l(t) = l, the height is h(t) = t 1 and the size (or weight ) is s(t) = P t i = n. See that t can be univocally written as t = t [m 1
1] ·t [m j
22] ·. . .·t [m j
k]
k
with t 1 > t j
2> · · · > t j
kand m i > 0. The following notations are useful when dealing with integer sequences, t <i = (t 1 , . . . , t i−1 ) (t ≤i = (t 1 , . . . , t i )) and t >i = (t i+1 , . . . , t l ) (t ≥i = (t i , . . . , t l )). The set LP(n) can be ordered with respect to the negative lexicographic order defined as follows: let t = (t 1 , . . . , t m ) and v = (v 1 , . . . , v l ) belong to LP(n), we set t< nlex v if and only if
∃i, 1 ≤ i ≤ min(l, m) : t j = v j , 1 ≤ j < i, t i > v i .
Analogously, a stack polyomino of size n can be represented by a unimodal sequence of size n, that is, an integer sequence t 1 , . . . , t l with P
i t i = n and such that t 1 ≤ t 2 ≤ . . . ≤ t i ≥ t i+1 ≥ . . . t l . We denote by US(n) the set of unimodal sequences of size n. A unimodal sequence t is univocally written as t = t <i · t [h] i · t >i+h , where t <i and the reversal of t >i+h are integer partitions of height at most t i − 1.
Definition 1 Given two unimodal sequences of size n, t = t <i · t [h] i · t >i+h and t 0 = t 0 <j · t 0[k] j · t 0 >j+k , we set t < t 0 if and only if t i > t 0 j or t i = t 0 j and h > k or t i = t 0 j , h = k and s(t <i ) > s(t 0 <j ) or t i = t 0 j , h = k, s(t <i ) = s(t 0 <j ) and t <i < nlex t 0 <j or t i = t 0 j , h = k, t <i = t 0 <j and t >i+h < nlex t 0 >j+k .
The vertical projection of P is the integer vector π(P ) = (π 1 , . . . , π l ) where l = w(P ) and for all i, with 1 ≤ i ≤ l, π i = ]{j|(i, j) ∈ P }. Moreover, the position vector of P is defined as the integer vector σ(P ) = (σ 1 , . . . , σ l ) where σ i = min{j|(i, j) ∈ P }, with 1 ≤ i ≤ l.
Given an integer vector v, with P
i v i = n, and a class of polyominoes A ⊆
CPol(n), we consider the set Π A (v) = {P ∈ A|π(P ) = v}. Any P ∈ A is
univocally described by a pair of integer sequences (v, p) where v = π(P ) and
p = σ(P ). We say that a vector p ∈ Z l is A-feasible with v ∈ N l if and only if
(v, p) identifies a polyomino P ∈ A.
(c)
(a) (b)
Figure 1: A convex polyomino (a), a stack polyomino (b), a Ferrer diagram (c).
2.1 Integer partitions with constraints
We consider the set LP h (n) ⊆ LP(n) of the integer partitions of n into parts smaller or equal to h. The smallest linear partition of LP h (n) is t = h [a] ·b where a = bn/hc and b = hni h , with l(t) = dn/he. In the sequel we are interested in generating LP h (n) by means of an efficient algorithm. We show that the same approach used in [15] can be used to design a CAT (Constant Amortized Time) algorithm which produces the ordered sequence (w.r.t < nlex ) of elements in LP h (n). In order to do that, we define a discrete dynamical system (with parameter h) whose states are all and only the elements of LP h (n). This system has an evolution rule called Move which simulates the movements of n grains stacked into a (two-dimensional) silo of height h and width n. Grains move to the right only. Informally, the rightmost grain of a plateau, say in column i, falls down to the first column j, with j > i, such that its height differs by at least 2.
More formally, one has:
Definition 2 Given t ∈ LP h (n) and an integer i, with 1 ≤ i ≤ l(t), let k be the first integer greater than i such that t i − t k ≥ 2 and t i − t j = 1 for all j with i < j < k (k is undefined, k = ⊥, if no such integer exists). Then
Move(t, i) =
t <i · (t i − 1, t i+1 , . . . , t k−1 , t k + 1) · t >k if k 6= ⊥
⊥ otherwise
We write t ⇒ t i 0 if t 0 = Move(t, i) and, more generally, t ⇒ v if there is a ? sequence of moves leading from t to v. We denote by G(t) = {v|t ⇒ v} the set ? of states which can be reached from t ∈ LP h (n). In particular, by reasoning as in [15, Lemma 3] one can easily prove:
Lemma 1 Let t = min <nlex (LP h (n)). Then, one has G(t) = LP h (n).
We denote by Rmost(t) the index indicating the rightmost move in t, Rmost(t) =
max{i|Move(t, i) 6= ⊥). The following definition is of particular interest for the
exhaustive generation of LP h (n).
a move
t A(t)
Figure 2: The grand ancestor of t = (5, 4, 3, 1, 1, 1, 1, 1) ∈ LP 6 (17).
Definition 3 Let t ∈ LP h (n) and i = Rmost(t). The grand ancestor of t is the integer partition A(t) = min <nlex {v ∈ LP h (n)|v ≤i = t ≤i , Move(v, i) 6= ⊥}.
From this definition it immediately follows:
Lemma 2 Let t ∈ LP h (n), i = Rmost(t) and q = P
j>i t j . Then, A(t) = t ≤i · (t i − 1) [a] · b. where a = b t q
i
−1 c and b = hqi t
i−1 .
When n and h are clear by the context, we denote by t (e) the eth integer partition in LP h (n). The following lemma states how to generate the ordered sequence of elements in LP h (n).
Lemma 3 Let t ∈ LP h (n). Then, for any e > 0, we have A(t (e) ) ⇒ t i
e(e+1) , with i e = Rmost(t (e) ).
Proof. We follow the proof of [16, Lemma 2.16], where a similar result applies to the set of states of a discrete dynamical system associated with the Ice Pile Model.
Let A(t (e) ) ⇒ v. By Lemma 2 and Definition 2 it follows that v = t i
e(e) <i
e
·(t i
e− 1) [a+1] · (b + 1) for suitable integers a and b. Suppose t (e+1) < nlex v and note that t (e+1) <i
e
= t (e) <i
e
. We distinguish two cases. If t (e+1) i
e
= t (e) i
e
− 1 = v i
eone necessarily has t (e+1) j = t (e) i
e
− 1 = v j , with i e < j ≤ i e + a, and t (e+1) i
e
+a+1 > b + 1 = v i
e+a+1 , that is, t (e+1) ∈ LP h (m), with m > n.
Otherwise, one has t (e+1) ≤i
e
= t (e) ≤i
e
and t (e) >i
e
< nlex t (e+1) >i
e
. Since i e = Rmost(t (e) ), the sequence t (e) >i
e
is equal to 1 [p] , for a suitable p ≥ 0. This means that t (e) >i
e
6< nlex t (e+1) >i
e
(otherwise t (e+1) >i
e