# Lexographic Unranking of Combinations Revisited
## 1 Introduction
However, to the best of our knowledge, these complexity analyses are only counting the number of calls to the function that computes a binomial coefficient, assuming that all the necessary coefficients have been pre-computed and stored (this pre-computation step is not included in the complexity analysis). From this fact, two questions arise. First, is this complexity analysis relevant? That is, does it faithfully reflect the actual runtime of the algorithms and can we afford the pre-computation of that many binomial coefficients? Second, among the different existing algorithms, which one performs best in practice? Using exact computations, it is actually not a problem to deal with combinations over sets of several thousands of objects. In this context, using a table filled with all possible binomial coefficients that might be needed is impractical. Most classical computer algebra systems (CAS) can unrank combinations in a reasonable time though, which suggests that there are better approaches. In Table 1, we present some of our experimental results. We detail everything in Section 4, but as a foretaste here we give some key points. In Section 2, we introduce a new unranking algorithm. The first column gives the typical run time of our C implementation of this algorithm. In the other columns, we give a rough performance comparison of four different CAS. For each one, we compare the average run time in milliseconds to unrank a combination first by using the native algorithm of the CAS (\"their algo.\") and second by implementing our new algorithm in the high-level programming language of the CAS. We observe a great diversity of run times in Table 1. Unfortunately, Maple, Mathematica, and MATLAB (to deal with integers with arbitrary precision in MATLAB, we use symbolic computations by calling the function sym) are all closed source so we cannot take a look at their implementation to understand these differences. However, a detailed study of the different algorithms from the literature and some practical considerations presented in Section 4 provide some insights on this question. Sagemath is a special case to us. Since version 9.1, our algorithm has been implemented (in Python 3) and is used as the native algorithm. \begin{table}
\begin{tabular}{l c c c c c c c c c} \hline \hline  & & \multicolumn{6}{c}{**Time in ms**} \\ \hline \multirow{2}{*}{**Sample**} & \multicolumn{3}{c}{**Sagemath**} & \multicolumn{3}{c}{**Maple**} & \multicolumn{3}{c}{**Mathematica**} & \multicolumn{3}{c}{**Matlab**} \\  & **Our Algo.** & **v. 9.0** & **v. 9.2** & **v. 2020.0** & **v. 12.1.0** & **v. 12.1.0** & **v. R2020b** \\  & **in C** & **Their Algo.** & **New Algo.** & **Their Algo.** & **Our Algo.** & **Their Algo.** & **Our Algo.** & **Their Algo.** & **Our Algo.** \\ \hline \(n=1000\) & 0.05464 & 2.6045 & 2.9672 & 78.2 & 2.12 & 0.44176 & 4.3145 & 3996.6 & 3041.2 \\ \(k=1000\) & 0.06052 & 8.8903 & 2.4784 & 614 & 2.96 & 0.34608 & 3.9547 & 3520.6 & 3380.0 \\ \(k=500\) & 0.17496 & 15.8968 & 8.7929 & 1180 & 13.2 & 5.9131 & 11.823 & 11,846 & 9315.2 \\ \hline \(n=3000\) & 0.27524 & 96.3589 & 8.0500 & 6130 & 19.2 & 4.9624 & 13.067 & 11,087 & 9879.4 \\ \(k=1500\) & & & & & & & & \\ \hline \(n=10000\) & 1.2554 & 191.03 & 31.665 & too long & 65.1 & 21.906 & 39.935 & too long & too long \\ \(k=1000\) & & & & & & & & \\ \hline \(n=10,000\) & 2.3849 & 2 245.6 & 29.027 & too long & 97.9 & 29.916 & 46.452 & too long & too long \\ \(k=5000\) & & & & & & & & \\ \hline \end{tabular}
\end{table} 
Table 1: Average time (in ms) for the unranking of a combination of \(k\) elements among \(n\) (_too long_ means that the average time is larger than 30,000 ms).