Lexicographic Unranking of Combinations Revisited
In the context of combinatorial sampling, the so-called “unranking method” 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 famili...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-03-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/14/3/97 |
| _version_ | 1827697221397643264 |
|---|---|
| author | Antoine Genitrini Martin Pépin |
| author_facet | Antoine Genitrini Martin Pépin |
| author_sort | Antoine Genitrini |
| collection | DOAJ |
| description | In the context of combinatorial sampling, the so-called “unranking method” 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 <i>k</i>-permutations. |
| first_indexed | 2024-03-10T13:04:06Z |
| format | Article |
| id | doaj.art-ad91101e96d043be872f0c71382d003a |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-03-10T13:04:06Z |
| publishDate | 2021-03-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-ad91101e96d043be872f0c71382d003a2023-11-21T11:16:19ZengMDPI AGAlgorithms1999-48932021-03-011439710.3390/a14030097Lexicographic Unranking of Combinations RevisitedAntoine Genitrini0Martin Pépin1<span style="font-variant: small-caps">CNRS</span>, Laboratoire de Paris 6—<span style="font-variant: small-caps">lip6</span>—<span style="font-variant: small-caps">umr</span> 7606, Sorbonne Université, F-75005 Paris, France<span style="font-variant: small-caps">CNRS</span>, Laboratoire de Paris 6—<span style="font-variant: small-caps">lip6</span>—<span style="font-variant: small-caps">umr</span> 7606, Sorbonne Université, F-75005 Paris, FranceIn the context of combinatorial sampling, the so-called “unranking method” 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 <i>k</i>-permutations.https://www.mdpi.com/1999-4893/14/3/97unranking algorithmcombinatorial generationcombinationlexicographic ordercomplexity analysis |
| spellingShingle | Antoine Genitrini Martin Pépin Lexicographic Unranking of Combinations Revisited Algorithms unranking algorithm combinatorial generation combination lexicographic order complexity analysis |
| title | Lexicographic Unranking of Combinations Revisited |
| title_full | Lexicographic Unranking of Combinations Revisited |
| title_fullStr | Lexicographic Unranking of Combinations Revisited |
| title_full_unstemmed | Lexicographic Unranking of Combinations Revisited |
| title_short | Lexicographic Unranking of Combinations Revisited |
| title_sort | lexicographic unranking of combinations revisited |
| topic | unranking algorithm combinatorial generation combination lexicographic order complexity analysis |
| url | https://www.mdpi.com/1999-4893/14/3/97 |
| work_keys_str_mv | AT antoinegenitrini lexicographicunrankingofcombinationsrevisited AT martinpepin lexicographicunrankingofcombinationsrevisited |