Gray Codes for Column-Convex Polyominoes
and a New Class of Distributive Lattices
Stirling Chow,
Department of Computer Science,
University of Victoria, Canada.
Frank Ruskey,
Department of Computer Science,
University of Victoria, Canada.
Abstract:
We introduce the problem of polyomino Gray codes, the listing of all
members of certain classes of polyominoes such that successive
polyominoes differ by some well-defined closeness condition, such
as the movement of one cell.
We discuss various closeness conditions and provide several Gray codes
for the class of column-convex polyominoes where the number of cells
in each column is fixed. For one of our closeness conditions there
is a natural new class of distributive lattice that arises.
The partial order is defined on the set of m-tuples
[S1] X [S2] X \cdots X [Sm], where
[S] = {0,1,...,S-1 } and each Si > 1.
The cover relations are
(p1,p2,...,pm) < (p1+1,p2,...,pm) and
(p1,p2,...,pj,pj+1,...,pm) <
(p1,p2,...,pj-1,pj+1+1,...,pm).
We also discuss some properties of this lattice.
-
The pdf file (uncorrected proof version).
-
Accepted (November 9, 2007) to appear in Discrete Mathematics
(special issue on De Bruijn cycles and generalized Gray codes).
Submitted July 20, 2006. It's now appeared:
Volume 309, Issue 17, 6 September 2009, Pages 5284-5297.
-
In press:
link to Elsevier.
Selected Publications that refer to this paper:
Back to list of publications.