We consider the class 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 in constant amortized time using O(n) space.
Hole-free Partially Directed Animals
paolo massazza
2019-01-01
Abstract
We consider the class 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 in constant amortized time using O(n) space.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
