The four basic functions in the lexicographic generation of the subsets of a given set
DOI:
https://doi.org/10.55630/mem.2026.55.087-097Keywords:
subset, lexicographic order, characteristic vector, successor, predecessor, ranking, unrankingAbstract
Here we apply a novel approach to generate subsets of a given set in lexicographic order and on this basis derive alternative functions for computing the successor and predecessor of a given subset. We also derive functions for ranking a given subset and unranking a given integer in a subset. We provide recursive and non-recursive implementations of these four basic functions. They run in linear time with respect to the cardinality of the given set and are easy to understand and use.
References
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.
