We describe a method which exploits discrete dynamical systems to generate suitable classes of polyominoes. We apply the method to design an algorithm that uses O(n) space to generate in constant amortized time all polyominoes corresponding to hole-free partially directed animals consisting of n sites on the square grid. By implementing the algorithm in C++ we have obtained a new sequence that does not appear in the On-Line Encyclopedia of Integer Sequences.
2
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
In this paper we consider the class of column-convex permutominoes, i.e. column-convex polyominoes defined by a pair of permutations (π1, π2). First, using a geometric construction, we prove that for every permutation π there is at least one column-convex permutomino P such that π1(P) = π or π2(P) = π. In the second part of the paper, we show how, for any given permutation π, it is possible to define a set of logical implications F(p) on the points of π, and prove that there exists a column-convex permutomino P such that π1(P) = π if and only if F(p) is satisfiable. This property can be then used to give a characterization of the set of column-convex permutominoes P such that π1(P) = π.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.