# Lexographic Unranking of Combinations Revisited
## 3 Classical Unranking Algorithms
### Unranking through Combinatics  
In 1887, [PERSON] [15] and later [PERSON] (detailed in the book [16] (p. 27)) presented an interesting way to decompose a natural number, in what we call today a mixed radix numeral system. In their case, it is the so-called combinatorial number system, or combinadics. The decomposition relies on binomial coefficients. **Fact 5**. : _Let \(n\geq k\) be two positive integers. For all integers \(u\), with \(0\leq u<{n\choose k}\), there exists a unique sequence \(0\leq c_{1}<c_{2}<\dots<c_{k}<n\) such that (we extend the definition of binomial coefficients with \({n\choose k}=0\) when \(k>n\))_  
\[u={c_{1}\choose 1}+{c_{2}\choose 2}+\dots+{c_{k-1}\choose k-1}+{c_{k}\choose k}.\]  
_The finite sequence \((c_{1},\dots,c_{k})\) is called the combinadic of \(u\)._  
For example, when \(n=5\) and \(k=3\), the number \(8\) is represented as \({1\choose 1}+{3\choose 2}+{4\choose 3}\), thus the combinadic of \(8\) is \((1,3,4)\). In Table 4, we present for various values of \(u\) the combinadic of \(u\) and the combination of rank \(u\) for \(n=6\) and \(k=2\). Here, we observe that the exhibited ranking is co-lexicographic and that the combination of rank \(u\) can be deduced from the combinadic of \(u\) by reversing it and applying the transformation \(x\mapsto n-1-x\) to each of its components. In 2004, using this representation, [PERSON] exhibited, in the MSDN article [27], an algorithm to build the \(u\)th element (in lexicographic order) of the combinations of \(k\) elements among \(n\). However, in fact, this algorithm was already published by [PERSON] and [PERSON] [26] (p. 47) and can also be seen as an extension of the work of [PERSON]. This algorithm is interesting as it corresponds to the previous implementation used in the mathematics software system Sagemath [28] (the previous unranking algorithm from Sagemath is stored in the Software Heritage Archive swh:1:cntc60366 bc03936 eede6509b23307321 af1035e23:lines=539-605). In the beginning of 2020, we replaced the Sagemath implementation by the algorithm presented in Section 2 (the new unranking algorithm from Sagemath is stored in the Software Heritage Archive swh:1:cntc:b2a68056554 dbf90 fa55e76820f348d9d55019e3:lines=539-653 (accessed on 15 March 2021)). The algorithm simply performs the combinadic decomposition of \(u\) and then applies the aforementioned transformation. The idea to get the combinadic of an integer \(0\leq u<{n\choose k}\) is the following: \(c_{k}\) is obtained as the maximum integer such that \(u\geq{c\choose k}\), and then the remaining part \(u-\binom{\binom{i}{k}}{k}\) is smaller than \(\binom{n-1}{k-1}\) so it can be decomposed recursively into a combinadic with \(k-1\) components smaller than \(n-1\). [PERSON]'s algorithm is described in Algorithm 4. ```
1:functionUnrankingViaCombinadic(\(n,k,u\))
2:\(L\leftarrow[0,\ldots,0]\)\(\triangleright\)\(k\) components
3:\(u^{\prime}\leftarrow\texttt{binomial}(n,k)-1-u\)
4:\(v\gets n\)
5:for\(i\) from \(0\) to \(k-1\)do
6:\(v\gets v-1\)
7:\(b\leftarrow\texttt{binomial}(v,k-i)\)
8:while\(u^{\prime}<b\)do
9:\(v\gets v-1\)
10:\(b\leftarrow\texttt{binomial}(v,k-i)\)
11:\(u^{\prime}\gets u^{\prime}-b\)
12:\(L[i]\gets n-1-v\)
13:return\(L\)
```
**Algorithm 4** Unranking a combination. As noted while explaining Table 4, we work with the reverse of the rank \(u\) (see Line 3 in the algorithm) in order to unrank combinations in lexicographic order. The presented algorithm is also close to [PERSON]'s algorithm [23] whose representation for combinations is distinct, but the computations are analogous; furthermore, in his paper, Theorem 2 corresponds exactly to the combinadic decomposition. The function UnrankingViaCombinadic(\(n,k,u\)) computes the combinations of \(k\) elements among \(n\) of rank \(u\) in lexicographic order, although the core of the algorithm is reverse co-lexicographic. The correctness of the algorithm is stated in [26]. Again, we express the complexity of this algorithm as its number of calls to the binomial function.