Алгоритмы комбинаторной генерации на основе структур деревьев И/ИЛИ для класса алгебраических производящих функций

В данной статье предложен систематический подход к разработке алгоритмов комбинаторной генерации для множеств дискретных структур, мощность которых задается коэффициентами алгебраических производящих функций и их степеней. Исследование базируется на наличии связи между операциями над производящими функциями и комбинаторными множествами. В качестве основы использован математический аппарат деревьев И/ИЛИ, который позволяет комбинировать алгоритмы комбинаторной генерации для простых подструктур в сложные комбинаторные объекты. При этом основным теоретическим результатом работы является вывод новых эффективных рекуррентных формул для вычисления значений коэффициентов алгебраических производящих функций и их степеней с полиномиальной вычислительной сложностью $O((n_1 + \ldots + n_m + m) \cdot n^2)$ по времени и $O(n^2)$ по памяти. На основе доказанных теорем о рекуррентных формулах, предложенный подход позволяет строить алгоритмы с полиномиальной оценкой вычислительной сложности, что делает их применимыми для решения практических задач в области прикладной дискретной математики и теоретической информатики. Кроме того, использование коэффициентов степеней производящих функций расширяет возможности генерации, так как это позволяет строить не только объекты исходного комбинаторного множества, связанного с производящей функцией, но и кортежи таких объектов. Апробация предложенного подхода показана на примерах получения рекуррентных формул и алгоритмов генерации на их основе для классических числовых последовательностей, таких как числа Фибоначчи, Пелля, Каталана, Моцкина и Шредера. Предложенный подход открывает новые возможности для решения задач оптимизации, моделирования и кодирования сложных дискретных структур, например, в таких областях как биоинформатика и криптография.

1. S. Kemp, “Digital 2024: Global overview report.” 2024, Accessed: Nov. 01, 2025. [Online]. Available: https://datareportal.com/reports/digital-2024-global-overview-report.

2. D. E. Knuth, The art of computer programming. Volume 4A: Combinatorial algorithms, part 1. USA: Addison-Wesley, 2011.

3. D. E. Knuth, The art of computer programming. Volume 4B: Combinatorial algorithms, part 2. USA: Addison-Wesley, 2022.

4. D. L. Kreher and D. R. Stinson, Combinatorial algorithms: Generation, enumeration, and search. USA: CRC Press, 1999.

5. E. Seyedi-Tabari, H. Ahrabian, and A. Nowzari-Dalini, “A new algorithm for generation of different types of RNA,” International Journal of Computer Mathematics, vol. 87, no. 6, pp. 1197–1207, 2010, doi: 10.1080/00207160802140049.

6. M. E. Nebel, A. Scheid, and F. Weinberg, “Random generation of RNA secondary structures according to native distributions,” Algorithms for Molecular Biology, vol. 6, p. 24, 2011, doi: 10.1186/1748-7188-6-24.

7. E. Onokpasa, S. Wild, and P. W. H. Wong, “RNA secondary structures: from ab initio prediction to better compression, and back,” in Data Compression Conference, 2023, pp. 278–287, doi: 10.1109/DCC55655.2023.00036.

8. M. Bellare, T. Ristenpart, P. Rogaway, and T. Stegers, “Format-preserving encryption,” Lecture Notes in Computer Science: International Workshop on Selected Areas in Cryptography, vol. 5867, pp. 295–312, 2009, doi: 10.1007/978-3-642-05445-7_19.

9. D. Luchaup, T. Shrimpton, T. Ristenpart, and S. Jha, “Formatted encryption beyond regular languages,” in ACM SIGSAC Conference on Computer and Communications Security, 2014, pp. 1292–1303, doi: 10.1145/2660267.266035.

10. A. V. Goldberg and M. Sipser, “Compression and ranking,” SIAM Journal on Computing, vol. 20, no. 3, pp. 524–536, 1991, doi: 10.1137/0220034.

11. Y. V. Shablya, “Compression of information objects using combinatorial generation methods based on AND/OR trees,” Proceedings of TUSUR University, vol. 27, no. 4, pp. 74–79, 2024, doi: 10.21293/1818-0442-2024-27-4-74-79.

12. Y. V. Shablya, D. V. Kruchinin, and V. V. Kruchinin, “Method for developing combinatorial generation algorithms based on AND/OR trees and its application,” Mathematics, vol. 8, no. 6, p. 962, 2020, doi: 10.3390/math8060962.

13. Y. V. Shablya, “A method for constructing combinatorial generation algorithms for context-free languages based on AND/OR tree structures,” Information Technologies, vol. 31, no. 9, pp. 465–476, 2025, doi: 10.17587/it.31.465-476.

14. Y. V. Shablya and D. V. Kruchinin, “Algorithms for ranking and unranking the combinatorial set of RNA secondary structures,” Discrete Mathematics, Algorithms and Applications, p. 2550059, 2025, doi: 10.1142/S1793830925500594.

15. P. Flajolet, P. Zimmerman, and B. Cutsem, “A calculus for the random generation of combinatorial structures,” Theoretical Computer Science, vol. 132, no. 1--2, pp. 1–35, 1994, doi: 10.1016/0304-3975(94)90226-7.

16. C. Martinez and X. Molinero, “A generic approach for the unranking of labeled combinatorial classes,” Random Structures and Algorithms, vol. 19, no. 3--4, pp. 472–497, 2001, doi: 10.1002/rsa.10025.

17. C. Martinez and X. Molinero, “Efficient iteration in admissible combinatorial classes,” Theoretical Computer Science, vol. 346, no. 2--3, pp. 388–417, 2005, doi: 10.1016/j.tcs.2005.08.028.

18. R. P. Stanley, Enumerative combinatorics. Volume 2. USA: Cambridge University Press, 1999.

19. A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The design and analysis of computer algorithms. USA: Addison-Wesley, 1974.

20. “The On-Line Encyclopedia of Integer Sequences.” 2025, Accessed: Nov. 01, 2025. [Online]. Available: http://www.oeis.org/.

21. D. V. Kruchinin, V. V. Kruchinin, and Y. V. Shablya, “On some properties of generalized Narayana numbers,” Quaestiones Mathematicae, vol. 45, no. 12, pp. 1949–1963, 2022, doi: 10.2989/16073606.2021.1980448.