Combinatorial Generation Algorithms for Some Lattice Paths Using the Method Based on AND/OR Trees
Methods of combinatorial generation make it possible to develop algorithms for generating objects from a set of discrete structures with given parameters and properties. In this article, we demonstrate the possibilities of using the method based on AND/OR trees to obtain combinatorial generation alg...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-05-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/16/6/266 |
| _version_ | 1797596479598100480 |
|---|---|
| author | Yuriy Shablya |
| author_facet | Yuriy Shablya |
| author_sort | Yuriy Shablya |
| collection | DOAJ |
| description | Methods of combinatorial generation make it possible to develop algorithms for generating objects from a set of discrete structures with given parameters and properties. In this article, we demonstrate the possibilities of using the method based on AND/OR trees to obtain combinatorial generation algorithms for combinatorial sets of several well-known lattice paths (North-East lattice paths, Dyck paths, Delannoy paths, Schroder paths, and Motzkin paths). For each considered combinatorial set of lattice paths, we construct the corresponding AND/OR tree structure where the number of its variants is equal to the number of objects in the combinatorial set. Applying the constructed AND/OR tree structures, we have developed new algorithms for ranking and unranking their variants. The performed computational experiments have confirmed the obtained theoretical estimation of asymptotic computational complexity for the developed ranking and unranking algorithms. |
| first_indexed | 2024-03-11T02:51:59Z |
| format | Article |
| id | doaj.art-9fc8075cb72e447d85d4e017deb2bae9 |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-03-11T02:51:59Z |
| publishDate | 2023-05-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-9fc8075cb72e447d85d4e017deb2bae92023-11-18T08:56:32ZengMDPI AGAlgorithms1999-48932023-05-0116626610.3390/a16060266Combinatorial Generation Algorithms for Some Lattice Paths Using the Method Based on AND/OR TreesYuriy Shablya0Laboratory of Algorithms and Technologies for Discrete Structures Research, Tomsk State University of Control Systems and Radioelectronics, 634050 Tomsk, RussiaMethods of combinatorial generation make it possible to develop algorithms for generating objects from a set of discrete structures with given parameters and properties. In this article, we demonstrate the possibilities of using the method based on AND/OR trees to obtain combinatorial generation algorithms for combinatorial sets of several well-known lattice paths (North-East lattice paths, Dyck paths, Delannoy paths, Schroder paths, and Motzkin paths). For each considered combinatorial set of lattice paths, we construct the corresponding AND/OR tree structure where the number of its variants is equal to the number of objects in the combinatorial set. Applying the constructed AND/OR tree structures, we have developed new algorithms for ranking and unranking their variants. The performed computational experiments have confirmed the obtained theoretical estimation of asymptotic computational complexity for the developed ranking and unranking algorithms.https://www.mdpi.com/1999-4893/16/6/266combinatorial generationrankingunrankingAND/OR treelattice pathDyck path |
| spellingShingle | Yuriy Shablya Combinatorial Generation Algorithms for Some Lattice Paths Using the Method Based on AND/OR Trees Algorithms combinatorial generation ranking unranking AND/OR tree lattice path Dyck path |
| title | Combinatorial Generation Algorithms for Some Lattice Paths Using the Method Based on AND/OR Trees |
| title_full | Combinatorial Generation Algorithms for Some Lattice Paths Using the Method Based on AND/OR Trees |
| title_fullStr | Combinatorial Generation Algorithms for Some Lattice Paths Using the Method Based on AND/OR Trees |
| title_full_unstemmed | Combinatorial Generation Algorithms for Some Lattice Paths Using the Method Based on AND/OR Trees |
| title_short | Combinatorial Generation Algorithms for Some Lattice Paths Using the Method Based on AND/OR Trees |
| title_sort | combinatorial generation algorithms for some lattice paths using the method based on and or trees |
| topic | combinatorial generation ranking unranking AND/OR tree lattice path Dyck path |
| url | https://www.mdpi.com/1999-4893/16/6/266 |
| work_keys_str_mv | AT yuriyshablya combinatorialgenerationalgorithmsforsomelatticepathsusingthemethodbasedonandortrees |