# Lexographic Unranking of Combinations Revisited
## 1 Introduction
### Combinatorial Context  
Throughout the paper, we represent combinations as follows.  
Definition 1: Let \(n\) and \(k\) be two integers with \(0\leq k\leq n\). We represent a combination of \(k\) elements among \(n\) elements denoted by \(\{0,1,\ldots,n-1\}\) as a finite increasingly sorted sequence containing \(k\) distinct elements.  
For example, let \(n\) and \(k\) be, respectively, \(5\) and \(3\). The finite sequences \((0,1,2)\) and \((0,2,4)\) are combinations of \(k\) elements among \(n\), but \((0,2,1)\) and \((0,1,2,3)\) are not. Other representations are sometimes used, notably by using a two-letter alphabet, but we stick to the one given in Definition 1 in this paper.  
There are several possible orders for comparing combinations. In the following, we restrict our attention to orders comparing combinations of the same length, i.e., the same number of elements.  
Definition 2: Let \(A=(a_{0},a_{1},\ldots,a_{k-1})\) and \(B=(b_{0},b_{1},\ldots,b_{k-1})\) be two distinct combinations of \(k\) elements among \(n\).  
* In the lexicographic order, we say that \(A\) is smaller than \(B\) if and only if both combinations have the same (possibly empty) prefix such that \((a_{0},\ldots,a_{p-1})=(b_{0},\ldots,b_{p-1})\) and if in addition \(a_{p}<b_{p}\).
* In the co-lexicographic order, we say that \(A\) is smaller than \(B\) if and only if the finite sequence \((a_{k-1},\ldots,a_{0})\) is smaller than \((b_{k-1},\ldots,b_{0})\) for the lexicographic order.
* If \(A\) is smaller than \(B\) for a given order, then, for the reverse order, \(B\) is smaller that \(A\).  
Definition 3: Let \(0\leq k\leq n\) be two integers and let \(A\) be a combination of \(k\) elements among \(n\). For a given order, the _rank_\(u\) of \(A\) belongs to \(\{0,1,\ldots(\frac{n}{k})-1\}\) and is such that \(A\) is the \(u\)th smallest combination.  
With these definitions in mind, we can enter the core of the paper organized as follows. We first give the presentation and a first complexity analysis of our new algorithm solving the lexicographic combination unranking problem in Section 2. Section 3 is dedicated to the survey of three classical algorithms for the latter problem. The first one is based on the so-called recursive method and the two other algorithms are based on combinacids, which is a specific numeral system. It seems that it is the first time that both are compared and the reason one is better is explained. We also propose a new method for their analysis based on a generating function approach. Obviously, we obtain the same results as in the literature, but we manage also to obtain better asymptotic bounds than in the literature. In Section 4, we then compare their efficiency experimentally (the implementation and the exhaustive material used for repeating the experiments are all available at [[http://github.com/[PERSON]](http://github.com/[PERSON])]([http://github.com/[PERSON]](http://github.com/[PERSON])) 3/combination_unranking (accessed on 15 March 2021)) and propose a way to improve the computation of the binomial coefficients used in all four algorithms. Surprisingly, once the improvements have been implemented in all algorithms, we observe deep similarities in their computations, which is reflected by their observed run times. Finally, we extend our approach to solve the problem of unranking structures enumerated by multinomial coefficients and also objects counted by the \(k\)-permutations of \(n\) (also called arrangements).