{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T02:46:32Z","timestamp":1760150792517,"version":"build-2065373602"},"reference-count":33,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2022,1,25]],"date-time":"2022-01-25T00:00:00Z","timestamp":1643068800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100006769","name":"Russian Science Foundation","doi-asserted-by":"publisher","award":["18-71-00059"],"award-info":[{"award-number":["18-71-00059"]}],"id":[{"id":"10.13039\/501100006769","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The presented research is devoted to the problem of developing new combinatorial generation algorithms for combinations. In this paper, we develop a modification of Ruskey\u2019s algorithm for unranking m-combinations of an n-set in co-lexicographic order. The proposed modification is based on the use of approximations to make a preliminary search for the values of the internal parameter k of this algorithm. In contrast to the original algorithm, the obtained algorithm can be effectively applied when n is large and m is small because the running time of this algorithm depends only on m. Furthermore, this algorithm can be effectively used when n and m are both large but n\u2212m is small, since we can consider unranking (n\u2212m)-combinations of an n-set. The conducted computational experiments confirm the effectiveness of the developed modification.<\/jats:p>","DOI":"10.3390\/a15020036","type":"journal-article","created":{"date-parts":[[2022,1,25]],"date-time":"2022-01-25T20:44:33Z","timestamp":1643143473000},"page":"36","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Unranking Small Combinations of a Large Set in Co-Lexicographic Order"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5564-2797","authenticated-orcid":false,"given":"Vladimir","family":"Kruchinin","sequence":"first","affiliation":[{"name":"Institute of Innovation, Tomsk State University of Control Systems and Radioelectronics, 634050 Tomsk, Russia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9695-7493","authenticated-orcid":false,"given":"Yuriy","family":"Shablya","sequence":"additional","affiliation":[{"name":"Department of Complex Information Security of Computer Systems, Tomsk State University of Control Systems and Radioelectronics, 634050 Tomsk, Russia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3412-432X","authenticated-orcid":false,"given":"Dmitry","family":"Kruchinin","sequence":"additional","affiliation":[{"name":"Department of Computer Control and Design Systems, Tomsk State University of Control Systems and Radioelectronics, 634050 Tomsk, Russia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3546-3921","authenticated-orcid":false,"given":"Victor","family":"Rulevskiy","sequence":"additional","affiliation":[{"name":"Department of Computer Control and Design Systems, Tomsk State University of Control Systems and Radioelectronics, 634050 Tomsk, Russia"}]}],"member":"1968","published-online":{"date-parts":[[2022,1,25]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Kreher, D.L., and Stinson, D.R. (1999). Combinatorial Algorithms: Generation, Enumeration, and Search, ACM.","DOI":"10.1145\/309739.309744"},{"key":"ref_2","unstructured":"Knuth, D.E. (2011). The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1, Addison-Wesley Professional."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Stojmenovic, I. (2007). Handbook of Applied Algorithms: Solving Scientific, Engineering and Practical Problems, John Wiley and Sons, Inc.. Chapter Generating all and Random Instances of a Combinatorial Object.","DOI":"10.1002\/9780470175668.ch1"},{"key":"ref_4","unstructured":"Ruskey, F. (2021, December 01). Combinatorial Generation. Working Version (1j-CSC 425\/520). Available online: http:\/\/page.math.tu-berlin.de\/~felsner\/SemWS17-18\/Ruskey-Comb-Gen.pdf."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1145\/355934.355937","article-title":"A comparison of combination generation methods","volume":"7","author":"Akl","year":"1981","journal-title":"ACM Trans. Math. Softw."},{"key":"ref_6","first-page":"103","article-title":"Algorithm 154: Combination in lexicographical order","volume":"6","author":"Mifsud","year":"1963","journal-title":"Comm. ACM"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01939357","article-title":"Generating combinations in parallel","volume":"26","author":"Chan","year":"1986","journal-title":"BIT Numer. Math."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1007\/BF01933707","article-title":"Parallel generation of permutations and combinations","volume":"26","author":"Chen","year":"1986","journal-title":"BIT Numer. Math."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/0020-0190(89)90192-0","article-title":"An optimal parallel algorithm for generating combinations","volume":"33","author":"Akl","year":"1989","journal-title":"Inform. Process. Lett."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1523","DOI":"10.1016\/0898-1221(89)90052-7","article-title":"A parallel algorithm for generating combinations","volume":"17","author":"Lin","year":"1989","journal-title":"Comput. Math. Appl."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/0167-8191(90)90125-S","article-title":"A systolic design for generating combinations in lexicographic order","volume":"13","author":"Tsay","year":"1990","journal-title":"Parallel Comput."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/0898-1221(92)90007-5","article-title":"A simple systolic algorithm for generating combinations in lexicographic order","volume":"24","author":"Stojmenovic","year":"1992","journal-title":"Comput. Math. Appl."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1142\/S0129626492000374","article-title":"Systolic generation of combinations from arbitrary elements","volume":"2","author":"Elhage","year":"1992","journal-title":"Parallel Process. Lett."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1006\/jpdc.1993.1030","article-title":"New methods for the generation of permutations, combinations, and other combinatorial objects in parallel","volume":"17","author":"Kapralski","year":"1993","journal-title":"J. Parallel Distrib. Comput."},{"key":"ref_15","unstructured":"Xu, C.W., Ma, X., and Shiue, W.K. (1996, January 9\u201311). A new parallel combination generator. Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, Sunnyvale, CA, USA."},{"key":"ref_16","unstructured":"Kokosinski, Z. (1997, January 9\u201311). On parallel generation of combinations in associative processor architectures. Proceedings of the IASTED International Conference on Parallel and Distributed Systems, Barcelona, Spain."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1590\/S0104-65002001000200009","article-title":"Generating permutations and combinations in lexicographical order","volume":"7","author":"Itai","year":"2001","journal-title":"J. Braz. Comput. Soc."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/0020-0190(84)90091-7","article-title":"An algorithm for generating subsets of fixed size with a strong minimal change property","volume":"19","author":"Eades","year":"1984","journal-title":"Inform. Process. Lett."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"292","DOI":"10.1093\/comjnl\/44.4.292","article-title":"On O(1) time algorithms for combinatorial generation","volume":"44","author":"Xiang","year":"2001","journal-title":"Comput. J."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1950060","DOI":"10.1142\/S1793830919500605","article-title":"A low spatial complexity algorithm to generate combinations with the strong minimal change property","volume":"11","year":"2019","journal-title":"Discret. Math. Algorithms Appl."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"5305","DOI":"10.1016\/j.disc.2007.11.048","article-title":"The coolest way to generate combinations","volume":"309","author":"Ruskey","year":"2009","journal-title":"Discret. Math."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1145\/360767.360811","article-title":"A numbering system for combinations","volume":"17","author":"Knott","year":"1974","journal-title":"Comm. ACM"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1080\/00207168508803468","article-title":"Lexicographic ordering, ranking and unranking of combinations","volume":"17","author":"Er","year":"1985","journal-title":"Int. J. Comput. Math."},{"key":"ref_24","unstructured":"Kokosinski, Z. (1995, January 19\u201321). Algorithms for unranking combinations and their applications. Proceedings of the IASTED\/ISMM International Conference on Parallel and Distributed Computing and Systems, Washington, DC, USA."},{"key":"ref_25","unstructured":"Kokosinski, Z. (1996, January 9\u201311). Unranking combinations in parallel. Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, Sunnyvale, CA, USA."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1515\/dma.1998.8.2.163","article-title":"Fast enumeration of combinatorial objects","volume":"8","author":"Ryabko","year":"1998","journal-title":"Discret. Math. Appl."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Shablya, Y., Kruchinin, D., and Kruchinin, V. (2020). Method for developing combinatorial generation algorithms based on AND\/OR trees and its application. Mathematics, 8.","DOI":"10.3390\/math8060962"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Genitrini, A., and Pepin, M. (2021). Lexicographic unranking of combinations revisited. Algorithms, 14.","DOI":"10.3390\/a14030097"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1016\/j.jda.2014.07.004","article-title":"Unranking of small combinations from large sets","volume":"29","author":"Shimizu","year":"2014","journal-title":"J. Discret. Algorithms"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Parque, V., and Miyashita, T. (2018, January 11\u201313). Towards the succinct representation of m out of n. Proceedings of the Internet and Distributed Computing Systems, Tokyo, Japan.","DOI":"10.1007\/978-3-030-02738-4_2"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Parque, V., and Miyashita, T. (2018, January 5\u20137). Unranking combinations using gradient-based optimization. Proceedings of the International Conference on Tools with Artificial Intelligence, Volos, Greece.","DOI":"10.1109\/ICTAI.2018.00094"},{"key":"ref_32","unstructured":"Roberts, A.W., and Varberg, D.E. (1973). Convex Functions, Academic Press."},{"key":"ref_33","unstructured":"Arfken, G.B., Weber, H.J., and Harris, F.E. (2012). Mathematical Methods for Physicists, Elsevier Academic Press."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/2\/36\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T22:07:08Z","timestamp":1760134028000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/2\/36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,25]]},"references-count":33,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2022,2]]}},"alternative-id":["a15020036"],"URL":"https:\/\/doi.org\/10.3390\/a15020036","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2022,1,25]]}}}