RESEARCH AND SOFTWARE IMPLEMENTATION OF COMBINATORIAL OBJECT GENERATION ALGORITHMS - KURYLO, Oleksandr; NITSAK , Vladyslav (Cherkasy University Bulletin: Applied Mathematics. Informatics, 2024)
Introduction. Combinatorics is one of the fundamental branches of discrete mathematics concerned with counting and constructing objects that satisfy given properties. Combinatorial objects – permutations, placements, and combinations – are widely used in probability theory, statistics, cryptography, and algorithm design. The generation of all possible configurations of such objects belongs to the class of NP problems, where the number of configurations grows factorially or exponentially with input size. Purpose. The aim of this work is to systematize the mathematical foundations of the main combinatorial objects, describe and compare algorithms for their generation implemented in Python using recursive and iterative approaches, and develop a software product with a graphical interface for visual demonstration. Results. The paper presents mathematical formulas for counting all six types of combinatorial objects (permutations, placements, and combinations, with and without repetition). Recursive and iterative generation algorithms are described and implemented in Python. The use of generators and the yield keyword is shown to provide an efficient approach to streaming generation of large sets of combinatorial objects. The recursive approach is more readable and natural but less memoryefficient; iterative algorithms with generators are preferable for practical use. A graphical application built with PyQt5 demonstrates the algorithms' results interactively. Conclusion. The generation of combinatorial objects is inherently NP in nature: the number of objects grows unmanageably fast even for moderate input values. Both recursive and iterative algorithms yield correct results; the choice between them depends on the specific requirements of readability, memory efficiency, and the size of input data. The developed software product can be used as an educational tool in mathematics and computer science classes.