A dynamical system approach to polyominoes generation. (English) Zbl 1519.68301
Summary: 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.
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 05B50 | Polyominoes |
| 11B83 | Special sequences and polynomials |
| 37E99 | Low-dimensional dynamical systems |
| 68W05 | Nonnumerical algorithms |
Software:
OEISReferences:
| [1] | Massazza P. Hole-Free Partially Directed Animals. In: Hofman P, Skrzypczak M (eds.), DLT19, volume 11647 ofLecture Notes in Comput. Sci.Springer. ISBN: 978-3-030-24886-4, 2019 pp. 221-233. · Zbl 1519.68300 |
| [2] | Golomb SW. Checker Boards and Polyominoes.Amer. Math. Monthly, 1954.61:675-682. doi:10.2307/ 2307321. · Zbl 0057.01005 |
| [3] | The Open Problems Project. URLhttp://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. · Zbl 1009.82010 |
| [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. · Zbl 07600801 |
| [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. · Zbl 0985.68516 |
| [8] | Bousquet-M´elou 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. · Zbl 0858.05006 |
| [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. · Zbl 1173.68761 |
| [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. · Zbl 1053.05006 |
| [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. · Zbl 1133.05019 |
| [12] | Massazza P.On the generation of convex polyominoes.Discrete Appl. Math., 2015.183:78-89. doi:10.1016/j.dam.2014.02.014. · Zbl 1307.05046 |
| [13] | Mantaci R, Massazza P. From Linear Partitions to Parallelogram Polyominoes. In: DLT11, volume 6795 ofLecture Notes in Comput. Sci.Springer, 2011 pp. 350-361. doi:10.1007/978-3-642-22321-1 30. · Zbl 1221.05034 |
| [14] | Massazza P. On the generation of L-convex polyominoes. In: Proc. of GASCom12, Bordeaux June 25-27. 2012. · Zbl 1307.05046 |
| [15] | Castiglione G, Massazza P. An efficient algorithm for the generation of Z-convex polyominoes. In: IWCIA 2014, volume 8466 ofLecture Notes in Comput. Sci.Springer, 2014 pp. 51-61. doi:10.1007/978-3-31907148-0 6. · Zbl 1486.68247 |
| [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. · Zbl 1358.05050 |
| [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. · Zbl 1427.05049 |
| [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. · Zbl 1435.05047 |
| [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. · Zbl 0930.05005 |
| [21] | Jensen I. Enumerations of Lattice Animals and Trees.Journal of Statistical Physics, 2001.102(3):865- 881. doi:10.1023/A:1004855020556. · Zbl 0999.82037 |
| [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¨ur 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. · Zbl 0178.00904 |
| [26] | Madras N. A pattern theorem for lattice clusters.Annals of Combinatorics, 1999.3(3):357-384. doi: 10.1007/BF01608793 · Zbl 0935.60089 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
