<?xml version="1.0" encoding="utf-8"?>
<TEI xmlns="http://www.tei-c.org/ns/1.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:hal="http://hal.archives-ouvertes.fr/" xmlns:gml="http://www.opengis.net/gml/3.3/" xmlns:gmlce="http://www.opengis.net/gml/3.3/ce" version="1.1" xsi:schemaLocation="http://www.tei-c.org/ns/1.0 http://api.archives-ouvertes.fr/documents/aofr-sword.xsd">
  <teiHeader>
    <fileDesc>
      <titleStmt>
        <title>HAL TEI export of hal-03040740v2</title>
      </titleStmt>
      <publicationStmt>
        <distributor>CCSD</distributor>
        <availability status="restricted">
          <licence target="https://creativecommons.org/publicdomain/zero/1.0/">CC0 1.0 - Universal</licence>
        </availability>
        <date when="2026-05-02T17:22:47+02:00"/>
      </publicationStmt>
      <sourceDesc>
        <p part="N">HAL API Platform</p>
      </sourceDesc>
    </fileDesc>
  </teiHeader>
  <text>
    <body>
      <listBibl>
        <biblFull>
          <titleStmt>
            <title xml:lang="en">Lexicographic unranking of combinations revisited</title>
            <author role="aut">
              <persName>
                <forename type="first">Antoine</forename>
                <surname>Genitrini</surname>
              </persName>
              <email type="md5">b04f9d15a460bdad6019bbd45c7a3ef7</email>
              <email type="domain">lip6.fr</email>
              <idno type="idhal" notation="string">antoinegenitrini</idno>
              <idno type="idhal" notation="numeric">881263</idno>
              <idno type="halauthorid" notation="string">500605-881263</idno>
              <idno type="IDREF">https://www.idref.fr/139245391</idno>
              <idno type="ISNI">http://isni.org/isni/0000000139952074</idno>
              <idno type="VIAF">https://viaf.org/viaf/187616094</idno>
              <idno type="ORCID">https://orcid.org/0000-0002-5480-0236</idno>
              <affiliation ref="#struct-541707"/>
            </author>
            <author role="aut">
              <persName>
                <forename type="first">Martin</forename>
                <surname>Pépin</surname>
              </persName>
              <idno type="halauthorid">1836819-0</idno>
              <affiliation ref="#struct-541707"/>
            </author>
            <editor role="depositor">
              <persName>
                <forename>Martin</forename>
                <surname>Pépin</surname>
              </persName>
              <email type="md5">dcad887a37dc23864eb1f835e6fe36fd</email>
              <email type="domain">unicaen.fr</email>
            </editor>
          </titleStmt>
          <editionStmt>
            <edition n="v1">
              <date type="whenSubmitted">2020-12-04 14:59:23</date>
            </edition>
            <edition n="v2" type="current">
              <date type="whenSubmitted">2021-02-22 11:01:08</date>
              <date type="whenModified">2025-04-04 09:46:03</date>
              <date type="whenReleased">2021-03-02 16:56:09</date>
              <date type="whenProduced">2021-03-19</date>
              <date type="whenEndEmbargoed">2021-02-22</date>
              <ref type="file" target="https://hal.sorbonne-universite.fr/hal-03040740v2/document">
                <date notBefore="2021-02-22"/>
              </ref>
              <ref type="file" subtype="author" n="1" target="https://hal.sorbonne-universite.fr/hal-03040740v2/file/preprint.pdf" id="file-3148374-2760246">
                <date notBefore="2021-02-22"/>
              </ref>
              <ref type="externalLink" target="https://www.mdpi.com/1999-4893/14/3/97/pdf"/>
            </edition>
            <respStmt>
              <resp>contributor</resp>
              <name key="1508191">
                <persName>
                  <forename>Martin</forename>
                  <surname>Pépin</surname>
                </persName>
                <email type="md5">dcad887a37dc23864eb1f835e6fe36fd</email>
                <email type="domain">unicaen.fr</email>
              </name>
            </respStmt>
          </editionStmt>
          <publicationStmt>
            <distributor>CCSD</distributor>
            <idno type="halId">hal-03040740</idno>
            <idno type="halUri">https://hal.sorbonne-universite.fr/hal-03040740</idno>
            <idno type="halBibtex">genitrini:hal-03040740</idno>
            <idno type="halRefHtml">&lt;i&gt;Algorithms&lt;/i&gt;, 2021, 14 (3), pp.97. &lt;a target="_blank" href="https://dx.doi.org/10.3390/a14030097"&gt;&amp;#x27E8;10.3390/a14030097&amp;#x27E9;&lt;/a&gt;</idno>
            <idno type="halRef">Algorithms, 2021, 14 (3), pp.97. &amp;#x27E8;10.3390/a14030097&amp;#x27E9;</idno>
            <availability status="restricted">
              <licence target="https://about.hal.science/hal-authorisation-v1/">HAL Authorization<ref corresp="#file-3148374-2760246"/></licence>
            </availability>
          </publicationStmt>
          <seriesStmt>
            <idno type="stamp" n="CNRS">CNRS - Centre national de la recherche scientifique</idno>
            <idno type="stamp" n="LIP6" corresp="SORBONNE-UNIVERSITE">Laboratoire d'Informatique de Paris 6</idno>
            <idno type="stamp" n="TDS-MACS">Réseau de recherche en Théorie des Systèmes Distribués, Modélisation, Analyse et Contrôle des Systèmes</idno>
            <idno type="stamp" n="SORBONNE-UNIVERSITE">Sorbonne Université</idno>
            <idno type="stamp" n="SORBONNE-UNIV" corresp="SORBONNE-UNIVERSITE">Sorbonne Université 01/01/2018</idno>
            <idno type="stamp" n="SU-SCIENCES" corresp="SORBONNE-UNIVERSITE">Faculté des Sciences de Sorbonne Université</idno>
            <idno type="stamp" n="TEST-HALCNRS">Collection test HAL CNRS</idno>
            <idno type="stamp" n="SU-TI">Sorbonne Université - Texte Intégral</idno>
            <idno type="stamp" n="ALLIANCE-SU"> Alliance Sorbonne Université</idno>
            <idno type="stamp" n="SUPRA_MATHS_INFO">Mathématiques + Informatique</idno>
          </seriesStmt>
          <notesStmt>
            <note type="audience" n="2">International</note>
            <note type="popular" n="0">No</note>
            <note type="peer" n="1">Yes</note>
          </notesStmt>
          <sourceDesc>
            <biblStruct>
              <analytic>
                <title xml:lang="en">Lexicographic unranking of combinations revisited</title>
                <author role="aut">
                  <persName>
                    <forename type="first">Antoine</forename>
                    <surname>Genitrini</surname>
                  </persName>
                  <email type="md5">b04f9d15a460bdad6019bbd45c7a3ef7</email>
                  <email type="domain">lip6.fr</email>
                  <idno type="idhal" notation="string">antoinegenitrini</idno>
                  <idno type="idhal" notation="numeric">881263</idno>
                  <idno type="halauthorid" notation="string">500605-881263</idno>
                  <idno type="IDREF">https://www.idref.fr/139245391</idno>
                  <idno type="ISNI">http://isni.org/isni/0000000139952074</idno>
                  <idno type="VIAF">https://viaf.org/viaf/187616094</idno>
                  <idno type="ORCID">https://orcid.org/0000-0002-5480-0236</idno>
                  <affiliation ref="#struct-541707"/>
                </author>
                <author role="aut">
                  <persName>
                    <forename type="first">Martin</forename>
                    <surname>Pépin</surname>
                  </persName>
                  <idno type="halauthorid">1836819-0</idno>
                  <affiliation ref="#struct-541707"/>
                </author>
              </analytic>
              <monogr>
                <idno type="halJournalId" status="VALID">98226</idno>
                <idno type="issn">1999-4893</idno>
                <title level="j">Algorithms</title>
                <imprint>
                  <publisher>MDPI</publisher>
                  <biblScope unit="volume">14</biblScope>
                  <biblScope unit="issue">3</biblScope>
                  <biblScope unit="pp">97</biblScope>
                  <date type="datePub">2021-03-19</date>
                </imprint>
              </monogr>
              <idno type="doi">10.3390/a14030097</idno>
            </biblStruct>
          </sourceDesc>
          <profileDesc>
            <langUsage>
              <language ident="en">English</language>
            </langUsage>
            <textClass>
              <keywords scheme="author">
                <term xml:lang="en">Unranking Algorithm</term>
                <term xml:lang="en">Combination</term>
                <term xml:lang="en">Lexicographic Order</term>
                <term xml:lang="en">Complexity Analysis</term>
              </keywords>
              <classCode scheme="halDomain" n="info.info-dm">Computer Science [cs]/Discrete Mathematics [cs.DM]</classCode>
              <classCode scheme="halDomain" n="info.info-ds">Computer Science [cs]/Data Structures and Algorithms [cs.DS]</classCode>
              <classCode scheme="halDomain" n="math.math-co">Mathematics [math]/Combinatorics [math.CO]</classCode>
              <classCode scheme="halTypology" n="ART">Journal articles</classCode>
              <classCode scheme="halOldTypology" n="ART">Journal articles</classCode>
              <classCode scheme="halTreeTypology" n="ART">Journal articles</classCode>
            </textClass>
            <abstract xml:lang="en">
              <p>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 like families counted by multinomial coefficients and k-permutations.</p>
            </abstract>
          </profileDesc>
        </biblFull>
      </listBibl>
    </body>
    <back>
      <listOrg type="structures">
        <org type="researchteam" xml:id="struct-541707" status="VALID">
          <orgName>Algorithmes, Programmes et Résolution</orgName>
          <orgName type="acronym">APR</orgName>
          <date type="start">2018-01-01</date>
          <desc>
            <address>
              <country key="FR"/>
            </address>
          </desc>
          <listRelation>
            <relation active="#struct-541703" type="direct"/>
            <relation active="#struct-413221" type="indirect"/>
            <relation name="UMR7606" active="#struct-441569" type="indirect"/>
          </listRelation>
        </org>
        <org type="laboratory" xml:id="struct-541703" status="VALID">
          <idno type="IdRef">13558292X</idno>
          <idno type="RNSR">199712651U</idno>
          <idno type="ROR">https://ror.org/05krcen59</idno>
          <orgName>LIP6</orgName>
          <date type="start">2018-01-01</date>
          <desc>
            <address>
              <addrLine>4 Place JUSSIEU 75252 PARIS CEDEX 05</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">http://www.lip6.fr/</ref>
          </desc>
          <listRelation>
            <relation active="#struct-413221" type="direct"/>
            <relation name="UMR7606" active="#struct-441569" type="direct"/>
          </listRelation>
        </org>
        <org type="regroupinstitution" xml:id="struct-413221" status="VALID">
          <idno type="IdRef">221333754</idno>
          <idno type="ROR">https://ror.org/02en5vm52</idno>
          <orgName>Sorbonne Université</orgName>
          <orgName type="acronym">SU</orgName>
          <date type="start">2018-01-01</date>
          <desc>
            <address>
              <addrLine>21 rue de l’École de médecine - 75006 Paris</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">http://www.sorbonne-universite.fr/</ref>
          </desc>
        </org>
        <org type="regroupinstitution" xml:id="struct-441569" status="VALID">
          <idno type="IdRef">02636817X</idno>
          <idno type="ISNI">0000000122597504</idno>
          <idno type="ROR">https://ror.org/02feahw73</idno>
          <orgName>Centre National de la Recherche Scientifique</orgName>
          <orgName type="acronym">CNRS</orgName>
          <date type="start">1939-10-19</date>
          <desc>
            <address>
              <country key="FR"/>
            </address>
            <ref type="url">https://www.cnrs.fr/</ref>
          </desc>
        </org>
      </listOrg>
    </back>
  </text>
</TEI>