# Lexographic Unranking of Combinations Revisited
## 3 Classical Unranking Algorithms
### Unranking through Combinatics
: _The average number of calls to binomial in Algorithm 4 for \(n\) being large and \(k\) being of the form an for \(0<\alpha<1\) is_  
\[\frac{u_{n,k}}{{n\choose k}}\underset{ \begin{subarray}{c}n\to\infty\\ k=an\end{subarray} }{=}n+2-\frac{1}{\alpha}+O\bigg{(}\frac{1}{n}\bigg{)}.\]  
In the literature, another algorithm based on combinadics is given in [22]. We provide a pseudo-code equivalent of the original Fortran algorithm in Algorithm 5. Note that the algorithm does not handle the case \(k=1\), which should thus be treated separately. There, in the computation of the combinadic for a given rank, the coefficients are computed from the smallest one, \(c_{1}\), to the second largest one, \(c_{k-1}\), and finally the value for \(c_{k}\) is directly deduced with no need for further trials. In this algorithm, the variable \(L\) contains the combinadic of \(u\) (not its reverse). We note two differences with Algorithm 4. First, the last coefficient (\(c_{k}\)) is directly computed without \"trying\" the different possible values as for the previous coefficients (see Line 13 ). Second, it uses a combinatorial argument to find the value of the \(c_{i}\) coefficients that is the complementary of the argument used in the previous algorithm: the number of sequences \(0\leq c_{1}<c_{2}<\dots<c_{k}<n\) with \(c_{1}\geq j\) is equal to \(\sum_{i=0}^{j}{n-i-1\choose k-1}\), hence the accumulation performed in the \(r\) variable. The fact that the same combinatorial argument can be used in two different ways here has to be put in parallel with Remark 1 at the beginning of this section. The first point mentioned above is an improvement over Algorithm 4, but in fact this second algorithm is penalized by the extra addition that it has to perform and then undo on Line 12 to find each \(c_{i}\). With this approach, it is mandatory to compute the accumulation of binomial coefficients in \(r\) until it becomes greater than \(u\) to know when to exit the loop. It appears in our experimentations in the next section that this has a noticeable impact on performance. ```
1:functionUnrankingViaCombinadic2(\(n,k,u\))
2:\(L\leftarrow[0,\dots,0]\)\(\triangleright\)\(k\) components
3:\(r\gets 0\)
4:for\(i\)from \(0\)to\(k-2\)do
5:if\(i\
eq 0\)then\(L[i]\gets L[i-1]\)
6:else\(L[i]\leftarrow-1\)
7:while true do
8:\(L[i]\gets L[i]+1\)
9:\(b\leftarrow\texttt{binomial}(n-L[i]-1,k-i-1)\)
10:\(r\gets r+b\)
11:if\(r>u\)then exit the loop
12:\(r\gets r-b\)
13:\(L[k-1]\gets L[k-2]+u-r+1\)
14:return\(L\)
```
**Algorithm 5** Unranking a combination (alternative algorithm). UnrankingViaCombinadic2(\(n,k,u\)) is a lexicographic unranking for combinations. This algorithm was presented by [PERSON] and [PERSON] [22], and its correctness is presented in [26]. Finally, note it is approximately the implementation in Matlab[29] whose code was also presented by [PERSON] ([7], p. 65). The latter approach also does trials to find the last coefficient of the combination instead of computing it directly on Line 13. **Lemma 5**. : _Let \(u_{n,k}\) be the cumulative numbers of calls to binomial while unranking all possible \(u\) from \(0\) to \(\binom{n}{k}-1\). For all \(n\), the sequence satisfies \(u_{n,k}=0\) when \(k=1,2\) or \(k>n\), and otherwise_  
\[u_{n,k}=\binom{n}{k}+u_{n-1,k-1}+u_{n-1,k}.\]  
The result is proved in an analogous way as Lemma 4, summing over \(c_{k-1}\) instead of \(c_{1}\). In Table 6, we compute the first values of \((u_{n,k})\). We note the first values are smaller than the previous ones, and Theorem 7 gives their asymptotic behavior. **Theorem 7**. : _Let \(U(z,y)\) be the generating functions associated with \((u_{n,k})\). Then,_  
\[U(z,y) =\frac{z^{2}\ y^{2}}{\left(1-z\right)^{2}\left(1-z-zy\right)^{2}};\ \text{thus}\] \[u_{n,k} =\binom{n}{k}\ \frac{k-1}{k+1}\ (n+1).\]  
**Corollary 5**. : _The average number of calls to binomial in Algorithm 5 for \(n\) being large and \(k\) being of the form an for \(0<\alpha<1\) is_  
\[\frac{u_{n,k}}{\binom{n}{k}}\underset{ \begin{subarray}{c}k=\alpha n\end{subarray}