Method for Developing Combinatorial Generation Algorithms Based on AND/OR Trees and Its Application
In this paper, we study the problem of developing new combinatorial generation algorithms. The main purpose of our research is to derive and improve general methods for developing combinatorial generation algorithms. We present basic general methods for solving this task and consider one of these me...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2020-06-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/8/6/962 |
| _version_ | 1797565499916156928 |
|---|---|
| author | Yuriy Shablya Dmitry Kruchinin Vladimir Kruchinin |
| author_facet | Yuriy Shablya Dmitry Kruchinin Vladimir Kruchinin |
| author_sort | Yuriy Shablya |
| collection | DOAJ |
| description | In this paper, we study the problem of developing new combinatorial generation algorithms. The main purpose of our research is to derive and improve general methods for developing combinatorial generation algorithms. We present basic general methods for solving this task and consider one of these methods, which is based on AND/OR trees. This method is extended by using the mathematical apparatus of the theory of generating functions since it is one of the basic approaches in combinatorics (we propose to use the method of compositae for obtaining explicit expression of the coefficients of generating functions). As a result, we also apply this method and develop new ranking and unranking algorithms for the following combinatorial sets: permutations, permutations with ascents, combinations, Dyck paths with return steps, labeled Dyck paths with ascents on return steps. For each of them, we construct an AND/OR tree structure, find a bijection between the elements of the combinatorial set and the set of variants of the AND/OR tree, and develop algorithms for ranking and unranking the variants of the AND/OR tree. |
| first_indexed | 2024-03-10T19:14:04Z |
| format | Article |
| id | doaj.art-73c30e33137941a7a74f62747f22dd9e |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-10T19:14:04Z |
| publishDate | 2020-06-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-73c30e33137941a7a74f62747f22dd9e2023-11-20T03:34:52ZengMDPI AGMathematics2227-73902020-06-018696210.3390/math8060962Method for Developing Combinatorial Generation Algorithms Based on AND/OR Trees and Its ApplicationYuriy Shablya0Dmitry Kruchinin1Vladimir Kruchinin2Department of Complex Information Security of Computer Systems, Tomsk State University of Control Systems and Radioelectronics, Tomsk 634050, RussiaDepartment of Complex Information Security of Computer Systems, Tomsk State University of Control Systems and Radioelectronics, Tomsk 634050, RussiaInstitute of Innovation, Tomsk State University of Control Systems and Radioelectronics, Tomsk 634050, RussiaIn this paper, we study the problem of developing new combinatorial generation algorithms. The main purpose of our research is to derive and improve general methods for developing combinatorial generation algorithms. We present basic general methods for solving this task and consider one of these methods, which is based on AND/OR trees. This method is extended by using the mathematical apparatus of the theory of generating functions since it is one of the basic approaches in combinatorics (we propose to use the method of compositae for obtaining explicit expression of the coefficients of generating functions). As a result, we also apply this method and develop new ranking and unranking algorithms for the following combinatorial sets: permutations, permutations with ascents, combinations, Dyck paths with return steps, labeled Dyck paths with ascents on return steps. For each of them, we construct an AND/OR tree structure, find a bijection between the elements of the combinatorial set and the set of variants of the AND/OR tree, and develop algorithms for ranking and unranking the variants of the AND/OR tree.https://www.mdpi.com/2227-7390/8/6/962combinatorial generationmethodalgorithmAND/OR treeEuler–Catalan’s trianglelabeled Dyck path |
| spellingShingle | Yuriy Shablya Dmitry Kruchinin Vladimir Kruchinin Method for Developing Combinatorial Generation Algorithms Based on AND/OR Trees and Its Application Mathematics combinatorial generation method algorithm AND/OR tree Euler–Catalan’s triangle labeled Dyck path |
| title | Method for Developing Combinatorial Generation Algorithms Based on AND/OR Trees and Its Application |
| title_full | Method for Developing Combinatorial Generation Algorithms Based on AND/OR Trees and Its Application |
| title_fullStr | Method for Developing Combinatorial Generation Algorithms Based on AND/OR Trees and Its Application |
| title_full_unstemmed | Method for Developing Combinatorial Generation Algorithms Based on AND/OR Trees and Its Application |
| title_short | Method for Developing Combinatorial Generation Algorithms Based on AND/OR Trees and Its Application |
| title_sort | method for developing combinatorial generation algorithms based on and or trees and its application |
| topic | combinatorial generation method algorithm AND/OR tree Euler–Catalan’s triangle labeled Dyck path |
| url | https://www.mdpi.com/2227-7390/8/6/962 |
| work_keys_str_mv | AT yuriyshablya methodfordevelopingcombinatorialgenerationalgorithmsbasedonandortreesanditsapplication AT dmitrykruchinin methodfordevelopingcombinatorialgenerationalgorithmsbasedonandortreesanditsapplication AT vladimirkruchinin methodfordevelopingcombinatorialgenerationalgorithmsbasedonandortreesanditsapplication |