A Dynamical System Approach to Polyominoes Generation

• Autorzy: Massazza Paolo

Identyfikatory

DOI

10.3233/FI-2021-2040

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

partially directed animals; polyominoes; exhaustive generation; algorithms; discrete dynamical system

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 180, nr 3
• Strony: 251--273
• Opis fizyczny: Bibliogr. 26 poz., rys., tab.

Twórcy

autor

Massazza Paolo

• Department of Theoretical and Applied Sciences, University of Insubria, Varese, Italy

Bibliografia

• [1] Massazza P. Hole-Free Partially Directed Animals. In: Hofman P, Skrzypczak M (eds.), DLT19, volume 11647 of Lecture Notes in Comput. Sci. Springer. ISBN: 978-3-030-24886-4, 2019 pp. 221-233.
• [2] Golomb SW. Checker Boards and Polyominoes. Amer. Math. Monthly, 1954. 61:675-682. doi:10.2307/2307321.
• [3] The Open Problems Project. URL http://cs.smith.edu/~jorourke/TOPP.
• [4] Jensen I, Guttmann AJ. Statistics of lattice animals (polyominoes) and polygons. Journal of Physics A: Mathematical and General, 2000. 33(29):L257-L263. doi:10.1088/0305-4470/33/29/102.
• [5] Barequet G, Rote G, Shalah M. λ > 4: an improved lower bound on the growth constant of polyominoes. Commun. ACM, 2016. 59(7):88-95. doi:10.1145/2851485.
• [6] Barequet G, Shalah M. Improved Upper Bounds on the Growth Constants of Polyominoes and Polycubes. In: Kohayakawa Y, Miyazawa FK (eds.), LATIN 2020: Theoretical Informatics. Springer International Publishing, Cham. ISBN: 978-3-030-61792-9, 2020 pp. 532-545.
• [7] Delest MP, Viennot G. Algebraic languages and polyominoes enumeration. Theor. Comput. Sci., 1984. 34(1-2):169-206. doi:10.1016/0304-3975(84)90116-6.
• [8] Bousquet-Mélou M. A method for the enumeration of various classes of column-convex polygons. Discrete Math., 1996. 154(1-3):1-25. doi:10.1016/0012-365X(95)00003-F.
• [9] Castiglione G, Restivo A. Reconstruction of L-convex polyominoes. Electron. Notes Discrete Math., 2003. 12:290-301. doi:10.1016/S1571-0653(04)00494-9.
• [10] Del Lungo A, Duchi E, Frosini A, Rinaldi S. On the Generation and Enumeration of some Classes of Convex Polyominoes. Electron. J. Comb., 2004. 11(1). doi:10.37236/1813.
• [11] Duchi E, Rinaldi S, Schaeffer G. The number of Z-convex polyominoes. Adv. Appl. Math., 2008. 40(1):54-72. doi:10.1016/j.aam.2006.07.004.
• [12] Massazza P. On the generation of convex polyominoes. Discrete Appl. Math., 2015. 183:78-89. doi:10.1016/j.dam.2014.02.014.
• [13] Mantaci R, Massazza P. From Linear Partitions to Parallelogram Polyominoes. In: DLT11, volume 6795 of Lecture Notes in Comput. Sci. Springer, 2011 pp. 350-361. doi:10.1007/978-3-642-22321-1_30.
• [14] Massazza P. On the generation of L-convex polyominoes. In: Proc. of GASCom12, Bordeaux June 25-27. 2012.
• [15] Castiglione G, Massazza P. An efficient algorithm for the generation of Z-convex polyominoes. In: IWCIA 2014, volume 8466 of Lecture Notes in Comput. Sci. Springer, 2014 pp. 51-61. doi:10.1007/978-3-319-07148-0_6.
• [16] Brocchi S, Castiglione G, Massazza P. On the exhaustive generation of k-convex polyominoes. Theor. Comput. Sci., 2017. 664:54-66. doi:http://dx.doi.org/10.1016/j.tcs.2016.02.006.
• [17] Formenti E, Massazza P. From Tetris to polyominoes generation. Electronic Notes in Discrete Mathematics, 2017. 59:79-98. doi:https://doi.org/10.1016/j.endm.2017.05.007.
• [18] Formenti E, Massazza P. On the Generation of 2-Polyominoes. In: Konstantinidis S, Pighizzini G (eds.), 20th International Conference on Descriptional Complexity of Formal Systems (DCFS), volume 10952 of Lecture Notes in Comput. Sci. Springer, 2018 pp. 101-113. doi:10.1007/978-3-319-94631-3\_9.
• [19] Redner S, Yang ZR. Size and shape of directed lattice animals. Journal of Physics A: Mathematical and General, 1982. 15(4):L177-L187. doi:10.1088/0305-4470/15/4/006.
• [20] Barcucci E, Lungo AD, Pergola E, Pinzani R. Directed animals, forests and permutations. Discrete Mathematics, 1999. 204(1-3):41-71. doi:10.1016/S0012-365X(98)00366-5.
• [21] Jensen I. Enumerations of Lattice Animals and Trees. Journal of Statistical Physics, 2001. 102(3):865-881. doi:10.1023/A:1004855020556.
• [22] Jensen I. Counting Polyominoes: A Parallel Implementation for Cluster Computing. In: Proceedings of the 2003 International Conference on Computational Science: Part III, ICCS’03. Springer-Verlag, 2003 pp. 203-212. doi:10.1007/3-540-44863-2_21.
• [23] Privman V, Barma M. Radii of gyration of fully and partially directed lattice animals. Zeitschrift für Physik B Condensed Matter, 1984. 57(1):59-63. doi:10.1007/BF01679926.
• [24] Redner S, Yang ZR. Size and shape of directed lattice animals. Journal of Physics A: Mathematical and General, 1982. 15(4):L177-L187. doi:10.1088/0305-4470/15/4/006.
• [25] Klarner DA. Cell Growth Problems. Canadian Journal of Mathematics, 1967. 19:851-863. doi:10.4153/CJM-1967-080-4.
• [26] Madras N. A pattern theorem for lattice clusters. Annals of Combinatorics, 1999. 3(3):357-384. doi:10.1007/BF01608793.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).