Method for Developing Combinatorial Generation Algorithms Based on AND/OR Trees and Its Application

Yuriy Shablya, Dmitry Kruchinin and Vladimir Kruchinin
Additional contact information
Yuriy Shablya: Department of Complex Information Security of Computer Systems, Tomsk State University of Control Systems and Radioelectronics, Tomsk 634050, Russia
Dmitry Kruchinin: Department of Complex Information Security of Computer Systems, Tomsk State University of Control Systems and Radioelectronics, Tomsk 634050, Russia
Vladimir Kruchinin: Institute of Innovation, Tomsk State University of Control Systems and Radioelectronics, Tomsk 634050, Russia

Mathematics, 2020, vol. 8, issue 6, 1-21

Abstract: 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.

Keywords: combinatorial generation; method; algorithm; AND/OR tree; Euler–Catalan’s triangle; labeled Dyck path; ranking algorithm; unranking algorithm (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/8/6/962/pdf (application/pdf)
https://www.mdpi.com/2227-7390/8/6/962/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:8:y:2020:i:6:p:962-:d:370480

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().