Random generation of combinatorial sets with special properties

• Autorzy: Grebennik I. , Lytvynenko O.
• Języki publikacji: EN

Abstrakty

EN

General approach for solving the problem of random generation of compositional k - images of combinatorial sets (k-sets) has been proposed. K-sets are powerful apparatus that can be applied for solving many scientific and applied problems. Though many literature is dedicated to the problem of generating combinatorial configurations, existing studies deals mostly with simple combinatorial configurations like combinations, permutations etc. The algorithms of generation both basic combinatorial sets and k-sets have been described. Algorithm for random generation of basic sets allows generating various combinatorial sets, and laws of constructing basic combinatorial sets can be pre-set. If identification of the laws fails, the algorithm allows using other algorithms to generate basic sets. Complexity of described algorithms has been evaluated. The complexity of the algorithm of generation k-sets is determined by the complexity of generation of basic sets, as well as the complexity of operations of nsubstitution and a number of levels of a certain k-set. The described approach to the random generation is very flexible since it allows obtaining various results by varying algorithm parameters. In its turn, it allows adjusting the number of elements for both basic sets and k-sets. The developed software allows solving the described problems of random generation of k -sets and basic combinatorial sets.

Słowa kluczowe

EN

combinatorial generation; k-set; Basic combinatorial set; random generation; complexity

• Wydawca: Polish Academy of Sciences, Branch in Lublin
• Czasopismo: ECONTECHMOD : An International Quarterly Journal on Economics of Technology and Modelling Processes
• Rocznik: 2016
• Tom: Vol. 5, No 4
• Strony: 43--48
• Opis fizyczny: Bibliogr. 21 poz., wykr., wz.

Twórcy

autor

Grebennik I.

• Kharkiv National University of Radio Electronics

autor

Lytvynenko O.

• Kharkiv National University of Radio Electronics

Bibliografia

• 1. Knuth D., 2005. The Art of Computer Programming, Volume 4, Fascicle 2: Generating All Tuples and Permutations. Addison-Wesley. – 144.
• 2. Knuth D., 2005. The Art of Computer Programming, Volume 4, Fascicle 3: Generating All Combinations and Partitions. Addison-Wesley.–160.
• 3. Kreher D., Stinson D., 1999. Combinatorial Algorithms: Generation Enumeration and Search. CRC Press. – 329.
• 4. Bona M., 2004. Combinatorics of Permutations. Chapman Hall-CRC. – 383.
• 5. Ruskey F., 2009. Combinatorial generation, Dept. of Computer Science Univ. of Victoria, Canada, 1j-CSC 425/520. – 289.
• 6. Korsh J., LaFollette P., 2004. Loopless array generation of multiset permutations // The Computer Journal. – Vol. 47, № 5. – 612–621.
• 7. Stoyan Y., Grebennik I., 2008. Description of Classes of Combinatorial Configurations by Mappings // Proc. of NAS of Ukraine.– 10. - 28-31. (in Russian).
• 8. Stoyan Y., Grebennik I., 2011. Description and Generation of Combinatorial Sets Having Special Characteristics // International Journal of Biomedical Soft Computing and Human Sciences. Special Volume “Bilevel Programming, Optimization Methods, and Applications to Economics” Vol. 18, №1. – 85-90.
• 9. Grebennik I., Lytvynenko O., 2012. Generating combinatorial sets with given properties // Cybernetics and Systems Analysis, 48(6). – 890–898.
• 10. Grebennik I., 2010. Description and generation of permutations containing cycles // Cybernetics and Systems Analysis, 46(6). – 945-952.
• 11. Grebennik I., Chorna O., 2015. Elements transpositions and their impact on the cyclic structure of permutations. // ECONTECHMOD. An International Quarterly Journal on Economics of Technology and Modelling Processes. – Vol. 4, № 3. – 33–38.
• 12. Grebennik I., Baranov A., Chorna O., Gorbacheva E., 2016. Optimization of linear function of a cyclic permutation based on the random search. // ECONTECHMOD. An International Quarterly Journal on Economics of Technology and Modelling Processes. – Vol. 5, № 3. – 211–216.
• 13. Bauslaugh B., Ruskey F., 1990. Generating alternating permutations lexicographically // BIT Numerical Mathematics. 30, 17–26.
• 14. Poneti M., Vajnovszki V., 2010. Generating restricted classes of involutions, Bell and Stirling permutations // European Journal of Combinatorics. 31, 553–564.
• 15. Bergeron F., Labelle G., Leroux P., 1998. Combinatorial Species and Tree-Like Structures. University Press, Cambridge.
• 16. De Bruijn N., 1970. Permutations with given ups and downs // Nieuw Arch. Wisk. 18 (3), 61–65.
• 17. Carlitz L., 1973. Permutations with prescribed pattern // Math Hachr, vol. 58, No. 1-6, 31–53.
• 18. Viennot G., 1979. Permutations ayant une forme donne // Discrete Mathematics. 26, 279–284.
• 19. Etienne G., 1984. Linear extensions of finie posets and a conjecture of G. Kreweras on permutations// Discrete Mathematics. 52, 107–112.
• 20. Shevelev V., 2012. The number of permutations with prescribed Up-down structure as a function of two variables // Integers. Volume 12.
• 21. Van Baronaigien R., Ruskey F., Ruskey D., 1992. Generating permutations with given ups and downs// Discrete Applied Mathematics. 36, 57–65.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).