Control Systems and Computers

https://doi.org/10.15407/csc.2021.01.015

Control Systems and Computers, 2021, Issue 1 (291), pp. 15-28.

UDC 519.816

Tymofijeva N.К., Doctor of Sciences (Eng.), Chief researcher, International Research and Training Center for Information Technologies and Systems of the NAS and MES of Ukraine, Glushkov ave., 40, Kyiv, 03187, Ukraine, tymnad@gmail.com

Using Periodicity Properties to Generate the Combinatorial Configurations

Introduction. Rules for generating combinatorial configurations are introduced. It is shown that the ordering of combinatorial sets is characterized by regularities due to which they are generated by the same procedures. This is a property of periodicity, which follows from the recurrent method of formation and ordering of combinatorial configurations. Based on it, a recurrent-periodic method has been developed, focused on generating combinatorial configurations of different types. With its help, the ordering of combinatorial configurations is carried out according to the same rules, and some of them are generated by different modifications of the same algorithm.

Formulation of the problem. Combinatorial sets can be ordered both chaotically and under strict rules. Analysis of these sets shows that they are ordered by the same procedures and there are patterns of their generation. One of such regularities, which is characteristic of many types of combinatorial configurations, is the property of periodicity, which follows from the recurrent method of their formation. The problem is to identify and formulate general rules by which combinatorial sets of different types and different orders are formed and ordered.

The proposed approach. To solve this problem, the structure of combinatorial sets is analyzed. This analysis shows that the formation of combinatorial configurations is carried out using three recurrent combinatorial operators, and their strict ordering is also performed according to three rules. That is, to generate combinatorial sets it is enough to specify the type of combinatorial configuration, the base set and the rules of their formation and ordering.

Conclusion. Identifying patterns of ordering of a certain combinatorial set allows to develop simple procedures for its generation for an arbitrary value  and to strictly prove that this set contains all non-identical combinatorial configurations. A characteristic feature of combinatorial sets is their formation from the base set according to given rules. For this purpose it is enough to enter the basic set  from which elements their formation is carried out, type of these objects and system of rules of their generation.

 Download full text! (On Ukrainian)

Keywords. combinatorial configuration, generation of combinatorial sets, periodicity property, combination without repetitions, permutations, division of a natural number.

1. Reinhold E., Nyverhelt Yu., Deo N., 1980. Kombinatornyye algoritmy. Teoriya i praktika, Translated from English, Mir, Moscow, 476 p. (In Russian).
2. Lypskyi V., 1988. Kombynatoryka dlya prohrammystov, Translated from Polish, Mir, Moscow, 213 p. (In Russian).
3. Endrius H., 1982. Teoriya razbieniĭ, Translated from English, Nauka, Moscow, 276 p. (In Russian).
4. Knut D., 1976. Iskusstvo programmirovaniya dlya EVM. Osnovnyye algoritmy, v 3 t. Translated from English, Mir, Moscow, T. 1, 735 p. (In Russian).
5. Lytvynenko O. S., 2018. “Metody heneratsiyi kombinatornykh konfihuratsiy ta yikh zastosu-vannya v matematychnomu i kompyuternomu modelyuvanni zadach perevezennya ta obrobky vantazhiv”, Abstract of Candidate of Technical Sciences, 01.05.02, In-t problem mashynobud. im. A. M. Pidhornoho, Kharkiv, 21 p. (In Ukrainian).
6. Rybnikov A., 1985. Vvedeniye v kombinatornyy analiz, Izd-vo Moscow. un-ta, Moscow, 308 p. (In Russian).
7. Tymofiyeva N. K., 2007. “Teoretyko-chyslovi metody rozvyazannya zadach kombinatornoyi optymizatsiyi”, Abstract of Doctor of Technical Sciences, In-t kibernetyky im. V. M. Hlushkova NAN Ukrayiny, Kyiv, 32 p. (In Ukrainian).
8. Berge C., 1968. Principes de combinatoire, Dunod, Paris, 154 p.
9. Sachkov V. N., 1977. Kombinatornyye metody diskretnoy matematiki, Nauka, Moscow, 319 p. (In Russian).
10. Tymofiyeva N. K., 2010. “Rekurentno-periodychnyy metod dlya heneruvannya kombinatornykh konfihuratsiy”, Kombinatorni konfihuratsiyi ta yikh zastosuvannya, Materialy desyatoho mizhvuzivskoho naukovo-praktychnoho seminaru (15-16 October 2010), Kirovohr. tekhn. un-t, Kirovohrad, pp. 138-141. (In Ukrainian).
11. Timofeeva N. K., 2002. “O nekotorykh svoystvakh razbiyeniy mnozhestva na podmnozhestva”, Upravlâûŝie sistemy i mašiny, 5, pp. 6-23. (In Russian).

Received 04.12.2020