Hole-Free Partially Directed Animals

摘要

We consider the class HFPDA of hole-free partially directed animals. This is the class of all polyominoes P such that every cell of P can be reached from any cell in the first column of P with a path (inside P) which makes only North, South and East steps, and such that there is not a finite region of empty unitary squares which is surrounded by cells belonging to P. We provide a generation algorithm that allows us to enumerate HFPDA(n) in constant amortized time using O(n) space.