Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Lexicographic unranking of combinations revisited

Abstract : 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.
Complete list of metadata

https://hal.sorbonne-universite.fr/hal-03040740
Contributor : Martin Pépin <>
Submitted on : Friday, December 4, 2020 - 2:59:23 PM
Last modification on : Tuesday, March 23, 2021 - 9:28:02 AM
Long-term archiving on: : Friday, March 5, 2021 - 7:10:52 PM

File

preprint.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03040740, version 1

Citation

Antoine Genitrini, Martin Pépin. Lexicographic unranking of combinations revisited. 2020. ⟨hal-03040740v1⟩

Share

Metrics

Record views

40

Files downloads

70