The four basic functions in the lexicographic generation of the subsets of a given set

Валентин Бакоев

doi:10.55630/mem.2026.55.087-097

Автори

Валентин Бакоев Факултет „Математика и информатика“, ВТУ „Св. св. Кирил и Mетодий“, Велико Търново, България https://orcid.org/0000-0003-2503-5325

DOI :

https://doi.org/10.55630/mem.2026.55.087-097

Ключови думи :

подмножество, лексикографска наредба, характеристичен вектор, следващо подмножество, предишно подмножество, номериране, деномериране

Абстракт

Тук прилагаме нов подход за генериране на подмножествата на дадено множество в лексикографска наредба и на тази основа извеждаме алтернативни функции за изчисляване на наследника и предшественика на дадено подмножество. Също така успяхме да изведем функции за номериране на дадено подмножество и деномерира- не на дадено цяло число в подмножество. Предоставяме рекурсивни и нерекурсивни реализации на тези четири основни функции. Те се изпълняват в линейно време спрямо мощността на даденото множество и са лесни за разбиране и използване.

Авторска биография

Автор: Валентин Бакоев, Факултет „Математика и информатика“, ВТУ „Св. св. Кирил и Mетодий“, Велико Търново, България

Факултет математика и информатика
ВТУ „Св. св. Кирил и Методий“
бул. „Арх. Георги Козаров“, № 1
5000 Велико Търново, България

Литература (библиография)

A. Aho, J. Hopcroft, J. Ullman, The Design and Analysis of Computer Algorithms. Addison-Wesley Publishing Company, 1974.

J. Arndt, MATTERS COMPUTATIONAL: Ideas, Algorithms, Source Code, Springer, 2011.

J. Arndt, Subset-lex: did we miss an order? https://arxiv.org/abs/1405.6503. Last accessed 12 Feb. 2026.

V. Bakoev, An Algorithm for Generating All Subsets in Lexicographic Order, 2022 International Conference Automatics and Informatics (ICAI), Varna, Bulgaria, (2022), 271–275.

V. Bakoev, Generating sets in lexicographic order and with minimal change, St. Cyril and St. Methodius Univ. Publ. House, Veliko Tarnovo, 2023. (monograph, in Bulgarian)

V. Bakoev, Binary vectors: orderings, integer sequences, and generating of sets, St. Cyril and St. Methodius Univ. Publ. House, Veliko Tarnovo, 2023. (monograph, in Bulgarian)

D. Knuth, The art of computer programming, Volume 4A: Combinatorial Algorithms, Part 1. Addison-Wesley, 2011.

D. Kreher, D. Stinson, Combinatorial algorithms: generation, enumeration and search, CRC Press, 1999.

A. Nijenhuis, H. Wilf, Combinatorial Algorithms for Computers and Calculators, 2nd ed., Academic Press, 1978.

OEIS Foundation Inc., The On-line Encyclopedia of Integer Sequences. https://oeis.org/. Last accessed 12 Feb. 2026

E. Reingold, J. Nievergelt, N. Deo, Combinatorial algorithms, Theory and practice. New Jersey, Prentice-Hall, 1977.

F. Ruskey, Combinatorial Generation.Working Version (1j-CSC 425/520), 2003. Available at http://page.math.tu-berlin.de/∼felsner/ SemWS17-18/Ruskey-Comb-Gen.pdf. Last accessed 12 Feb. 2026

S. Skiena, The Algorithm Design Manual. 2nd ed., Springer-Verlag London Limited, 2008.

I. Stojmenović, M. Miyakawa, Applications of a subset generating algorithm to base enumeration, knapsack and minimal covering problems. The Computer Journal, Vol. 31, No. 1, (1988), 65–70.