Lexicographic unranking of combinations revisited - Sorbonne Université
Pré-Publication, Document De Travail Année : 2020

Lexicographic unranking of combinations revisited

Résumé

We propose a comparative study of four algorithms dedicated to the lexicographic unranking of combinations. Three of them are algorithms from the literature. We analyze their time complexity in average, with a uniform presentation, and describe their strengths and weaknesses. Furthermore we also introduce a new algorithm using a new strategy of computations inside the classical factorial numeral system (or factoradics). Then after proposing improvements for all implementations we present a detailed complexity analysis whose results are validated by an experimental analysis for actual use of combination unranking. Interestingly we show that even if the algorithms are based on different strategies all are doing very similar computations. Finally successfully apply our approach to the unranking of other classical combinatorial objects.
Fichier principal
Vignette du fichier
preprint.pdf (677.11 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03040740 , version 1 (04-12-2020)
hal-03040740 , version 2 (22-02-2021)

Identifiants

  • HAL Id : hal-03040740 , version 1

Citer

Antoine Genitrini, Martin Pépin. Lexicographic unranking of combinations revisited. 2020. ⟨hal-03040740v1⟩
410 Consultations
643 Téléchargements

Partager

More