# Lexographic Unranking of Combinations Revisited
## 2 Unranking through Factoradics: A New Strategy
### Combinations Unranking through Factoradics
The key to the rank conversion is also Fact 2. As a consequence, we get that the first \(\binom{n-1}{k-1}\) such sequences (in co-lexicographic order) have \(f_{n-1}=0\) and that the \(\binom{n-1}{k}\) following have \(f_{n-1}\geq 1\). Once again, we opt for a simple presentation here where the rank conversion and the unranking part of the algorithm are clearly separated. There is much room for improvement here: for instance, note that, at the end of the function RankConversion, a factoradic decomposition is transformed into the integer it represents, but then at the beginning of UnrankingPermutation this integer will be decomposed again in factoradics. In fact, instead of storing \(m\) into \(F\) on Line 8 we could directly compute the \(i\)th component of the combination as \(m+i\) by using the remark at the beginning of the proof of Lemma 1. In Section 4.2, we provide a more efficient way to implement this algorithm including this particular optimization and other improvements. **Proposition 2**. : _The function UnrankingCombination\((n,k,u)\) computes the \(u\)th combination of \(k\) elements among \(n\) in lexicographic order._  
Proof. : The algorithm, and thus its proof, relies heavily on Fact 2. The key to prove the correctness of the RankConversion function is the following loop invariant:  
* The values of \(f_{n-1-j}\) for all \(0\leq j<i\) have been computed and stored in \(F\). * The value of \(f_{n-i-1}\) (which has not been determined yet, as we enter the loop) is at least \(m\). * The variable \(u^{\prime}\) holds the rank of the sequence \(\left(f_{j}\right)_{0\leq j<n-i}\) (note that \(j<i\)) among all sequences satisfying the condition of Fact 2 with \(k=k-i\) and \(n=n-i\). With this invariant at hand, the combinatorial argument behind the condition \(u<\binom{n-m-i-1}{k-i-1}\) in the algorithm becomes more apparent; that is, the binomial coefficient counts the number of such sequences ending with \(m\). Hence, if \(u<\binom{n-m-i-1}{k-i-1}\), then \(f_{n-1-i}=m\) and we move to the evaluation of the next coefficient (\(f_{n-i-2}\)); otherwise, we try the next possible value for \(m\). ```
1:functionRankConversion\((n,k,u)\)
2:\(F\leftarrow[0,\ldots,0]\)\(\triangleright\)\(n\) components in \(F\)
3:\(i\gets 0\)
4:\(m\gets 0\)
5:while\(i<k\)do
6:\(b\leftarrow\texttt{binomial}(n-1-m-i,k-1-i)\)
7:if\(b>u\)then
8:\(F[n-1-i]\gets m\)
9:\(i\gets i+1\)
10:else
11:\(u\gets u-b\)
12:\(m\gets m+1\)
13:\(\triangleright\)\(F\) is the factoradic decomposition
14:return\(\texttt{composition}(F)\)
```
**Algorithm 2** Unranking a combination. The usual way to evaluate the efficiency of such an algorithm is to count the number of times the binomial function is called (see, e.g., the book [7] (p. 66) or the papers [22; 23]). During the conversion from the rank of the combination to the one of the associated permutation, the coefficients are obtained via trials (in the factoradic notation) for \(f_{n-1}\) to \(f_{n-k}\), remarking that through our bijection \(\mathcal{P}_{n,k}\) the latter sequence is weakly increasing. Thus, the worst cases are obtained when the value \(f_{n-k}\) is as large as possible, that is \(n-k\). In these cases, the number of calls to binomial is \(n\). To study the _average_ number of calls to binomial, when \(u\) describes the whole range from \(0\) to \((\binom{n}{k}-1\), we introduce the following cumulative sequence. **Lemma 2**. : _Let \(u_{n,k}\) be the cumulative numbers of calls to binomial while unranking all possible combinations \(u\) from \(0\) to \((\binom{n}{k}-1\). The sequence satisfies: \(u_{n,0}=0\) and \(u_{n,n+i}=0\) for all \(n\) and \(i>0\), and otherwise:_  
\[u_{n,k}=\binom{n}{k}+u_{n-1,k-1}+u_{n-1,k}.\]  
In Table 2, we give the first values of \(u_{n,k}\), when \(n\) is less than \(9\). The obtained sequence is stored under the reference OEIS A127717 (throughout this paper, a reference OEIS A\(\cdots\) points to Sloane's Online Encyclopedia of Integer Sequences www.oeis.org (accessed on 15 March 2021)).