| Title: |
Lexicographic unranking algorithms for the Twentyfold Way |
| Authors: |
Curiel, Amaury; Genitrini, Antoine |
| Contributors: |
Algorithmes, Programmes et Résolution (APR); LIP6; Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS); ANR-25-CE48-0602,COMETA-GAE,COMbinatoire énumérative ET Applications: Génération Aléatoire et Exhaustive(2025); ANR-23-CE48-0014,PANDAG,Analyse de paramètres de classes de DAGS(2023) |
| Source: |
https://hal.science/hal-05486059 ; 2026. |
| Publisher Information: |
CCSD |
| Publication Year: |
2026 |
| Subject Terms: |
Twentyfold Way; Twelvefold Way; Unranking; Combinatorial generation; Lexicographic order; Thirtyfold Way; [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] |
| Description: |
The Twelvefold Way, introduced by Rota, provides a fundamental framework for classifying and counting functions between finite sets. While counting formulas for these cases are well-established, efficient lexicographic unranking algorithms (which map an integer to its corresponding combinatorial structure) remain missing for several key cases, most notably those related to set partitions. In this paper, we extend the study of combinatorial generation to the Twentyfold Way, a broader classification that incorporates more complex combinatorial objects. Our primary contribution is the development of the first lexicographic unranking algorithms for the cases that had previously remained unaddressed, specifically set partitions and their ordered counterparts. The core of our approach lies in the derivation of new counting formulas based on shared prefixes. By decomposing the combinatorial space according to lexicographical prefixes, we establish a direct bridge between recursive counting and unranking. We further provide efficient algorithmic implementations capable of handling the very large integers inherent in these problems. Our complexity analysis and experimental results demonstrate that these algorithms offer a robust and efficient solution for unranking and uniform random generation. |
| Document Type: |
report |
| Language: |
English |
| Availability: |
https://hal.science/hal-05486059; https://hal.science/hal-05486059v1/document; https://hal.science/hal-05486059v1/file/CurielGenitrini_vHAL.pdf |
| Rights: |
https://creativecommons.org/licenses/by/4.0/ ; info:eu-repo/semantics/OpenAccess |
| Accession Number: |
edsbas.2ABE5C90 |
| Database: |
BASE |