{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,9]],"date-time":"2026-03-09T06:27:53Z","timestamp":1773037673110,"version":"3.50.1"},"reference-count":30,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2021,3,19]],"date-time":"2021-03-19T00:00:00Z","timestamp":1616112000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>In the context of combinatorial sampling, the so-called \u201cunranking method\u201d can be seen as a link between a total order over the objects and an effective way to construct an object of given rank. The most classical order used in this context is the lexicographic order, which corresponds to the familiar word ordering in the dictionary. In this article, we propose a comparative study of four algorithms dedicated to the lexicographic unranking of combinations, including three algorithms that were introduced decades ago. We start the paper with the introduction of our new algorithm using a new strategy of computations based on the classical factorial numeral system (or factoradics). Then, we present, in a high level, the three other algorithms. For each case, we analyze its time complexity on average, within a uniform framework, and describe its strengths and weaknesses. For about 20 years, such algorithms have been implemented using big integer arithmetic rather than bounded integer arithmetic which makes the cost of computing some coefficients higher than previously stated. We propose improvements for all implementations, which take this fact into account, and we give a detailed complexity analysis, which is validated by an experimental analysis. Finally, we show that, even if the algorithms are based on different strategies, all are doing very similar computations. Lastly, we extend our approach to the unranking of other classical combinatorial objects such as families counted by multinomial coefficients and k-permutations.<\/jats:p>","DOI":"10.3390\/a14030097","type":"journal-article","created":{"date-parts":[[2021,3,21]],"date-time":"2021-03-21T22:00:37Z","timestamp":1616364037000},"page":"97","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Lexicographic Unranking of Combinations Revisited"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5480-0236","authenticated-orcid":false,"given":"Antoine","family":"Genitrini","sequence":"first","affiliation":[{"name":"<span style=\"font-variant: small-caps\">CNRS<\/span>, Laboratoire de Paris 6\u2014<span style=\"font-variant: small-caps\">lip6<\/span>\u2014<span style=\"font-variant: small-caps\">umr<\/span> 7606, Sorbonne Universit\u00e9, F-75005 Paris, France"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1892-3017","authenticated-orcid":false,"given":"Martin","family":"P\u00e9pin","sequence":"additional","affiliation":[{"name":"<span style=\"font-variant: small-caps\">CNRS<\/span>, Laboratoire de Paris 6\u2014<span style=\"font-variant: small-caps\">lip6<\/span>\u2014<span style=\"font-variant: small-caps\">umr<\/span> 7606, Sorbonne Universit\u00e9, F-75005 Paris, France"}]}],"member":"1968","published-online":{"date-parts":[[2021,3,19]]},"reference":[{"key":"ref_1","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_2","unstructured":"Grebennik, I., and Lytvynenko, O. (2017, January 3\u20134). Developing software for solving some combinatorial generation and optimization problems. Proceedings of the 7th International Conference on Application of Information and Communication Technology and Statistics in Economy and Education, Sofia, Bulgaria."},{"key":"ref_3","first-page":"2437","article-title":"Parallel Algorithm for Learning Optimal Bayesian Network Structure","volume":"12","author":"Tamada","year":"2011","journal-title":"J. Mach. Learn. Res."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"464","DOI":"10.1109\/TR.2007.903229","article-title":"k-out-of-n:G System Reliability With Imperfect Fault Coverage","volume":"56","author":"Myers","year":"2007","journal-title":"IEEE Trans. Reliab."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Bodini, O., Genitrini, A., and Naima, M. (2019, January 6). Ranked Schr\u00f6der Trees. Proceedings of the Sixteenth Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2019, San Diego, CA, USA.","DOI":"10.1137\/1.9781611975505.2"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"5781","DOI":"10.1021\/acsomega.9b03848","article-title":"Peptide Combination Generator: A Tool for Generating Peptide Combinations","volume":"5","author":"Ali","year":"2020","journal-title":"ACS Omega"},{"key":"ref_7","unstructured":"Ruskey, F. (2003). Combinatorial Generation, Available online: https:\/\/citeseerx.ist.psu.edu\/viewdoc\/summary?doi=10.1.1.93.5967."},{"key":"ref_8","unstructured":"Knuth, D.E. (2011). The Art of Computer Programming, Volume 4A, Combinatorial Algorithms, Addison-Wesley Professional."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Skiena, S. (2020). The Algorithm Design Manual, Third Edition, Springer. Texts in Computer Science.","DOI":"10.1007\/978-3-030-54256-6"},{"key":"ref_10","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_11","unstructured":"Nijenhuis, A., and Wilf, H.S. (1975). Combinatorial Algorithms, Academic Press. Computer Science and Applied Mathematics."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(94)90226-7","article-title":"A calculus for the random generation of labelled combinatorial structures","volume":"132","author":"Flajolet","year":"1994","journal-title":"Theor. Comput. Sci."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"472","DOI":"10.1002\/rsa.10025","article-title":"A generic approach for the unranking of labeled combinatorial classes","volume":"19","author":"Molinero","year":"2001","journal-title":"Random Struct. Algorithms"},{"key":"ref_14","unstructured":"Hamza, M.H. (1995, January 19\u201321). Algorithms for Unranking Combinations and their Applications. Proceedings of the Seventh IASTED\/ISMM International Conference on Parallel and Distributed Computing and Systems, Washington, DC, USA."},{"key":"ref_15","first-page":"45","article-title":"Sopra una formula numerica","volume":"25","author":"Pascal","year":"1887","journal-title":"G. Di Mat."},{"key":"ref_16","unstructured":"Beckenbach, E.F., and P\u00f3lya, G. (1981). Applied Combinatorial Mathematics, R.E. Krieger Publishing Company."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"176","DOI":"10.24033\/bsmf.378","article-title":"Sur la num\u00e9ration factorielle, application aux permutations","volume":"16","author":"Laisant","year":"1888","journal-title":"Bull. Soc. Math. Fr."},{"key":"ref_18","unstructured":"Fisher, R.A., and Yates, F. (1948). Statistical Tables for Biological, Agricultural and Medical Research, Oliver & Boyd."},{"key":"ref_19","unstructured":"Bonet, B. (2008). Efficient algorithms to rank and unrank permutations in lexicographic order. AAAI Workshop on Search in AI and Robotics\u2014Technical Report, The AAAI Press."},{"key":"ref_20","first-page":"39","article-title":"A Quantitative Study of Pure Parallel Processes","volume":"23","author":"Bodini","year":"2016","journal-title":"Electron. J. Comb."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"420","DOI":"10.1145\/364520.364540","article-title":"Algorithm 235: Random Permutation","volume":"7","author":"Durstenfeld","year":"1964","journal-title":"Commun. ACM"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1145\/355732.355739","article-title":"Algorithm 515: Generation of a Vector from the Lexicographical Index [G6]","volume":"3","author":"Buckles","year":"1977","journal-title":"ACM Trans. Math. Softw."},{"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","doi-asserted-by":"crossref","unstructured":"Flajolet, P., and Sedgewick, R. (2009). Analytic Combinatorics, Cambridge University Press.","DOI":"10.1017\/CBO9780511801655"},{"key":"ref_25","unstructured":"Flajolet, P., and Sedgewick, R. (2013). An Introduction to the Analysis of Algorithms, Addison Wesley. [2nd ed.]."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Kreher, D.L., and Stinson, D.R. (1999). Combinatorial Algorithms: Generation, Enumeration, and Search, CRC Press.","DOI":"10.1145\/309739.309744"},{"key":"ref_27","unstructured":"McCaffrey, J. (2021, March 15). Generating the mth Lexicographical Element of a Mathematical Combination. MSDN. Available online: http:\/\/docs.microsoft.com\/en-us\/previous-versions\/visualstudio\/aa289166(v=vs.70)."},{"key":"ref_28","unstructured":"The Sage Developers (2021, March 15). SageMath, the Sage Mathematics Software System (Version 9.2), Available online: https:\/\/www.sagemath.org\/."},{"key":"ref_29","unstructured":"Butler, B. (2021, March 15). Function kSubsetLexUnrank, MATLAB Central File Exchange. Available online: http:\/\/fr.mathworks.com\/matlabcentral\/fileexchange\/53976-combinatorial-numbering-rank-and-unrank."},{"key":"ref_30","unstructured":"Bostan, A., Chyzak, F., Giusti, M., Lebreton, R., Lecerf, G., Salvy, B., and Schost, E. (2017). Algorithmes Efficaces en Calcul Formel, Printed by CreateSpace. [10th ed.]."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/3\/97\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T05:38:26Z","timestamp":1760161106000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/3\/97"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,19]]},"references-count":30,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2021,3]]}},"alternative-id":["a14030097"],"URL":"https:\/\/doi.org\/10.3390\/a14030097","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,3,19]]}}}