# Lexographic Unranking of Combinations Revisited
## 4 Improving Efficiency and Realistic Complexity Analysis
### Improving the Implementations of the Algorithms  
Before going further with the experiments, we propose an improvement in the computation of the binomial coefficient, which is applicable to all algorithms presented in this paper. In all of the presented algorithms, a binomial coefficient is computed at each step of the generation. There are various ways to implement those. One possibility is to compute the two products \(n\cdot(n-1)\cdot(n-2)\cdots(n-k+1)\) and \(k!\) separately using a divide and conquer strategy as described in [30] (Section 15.3) and then to compute the division. In the unranking algorithms, instead of doing the \"full\" evaluation of the binomial coefficient at each step, it is possible to reuse the computations from the previous step and obtain the value of the new coefficient by a constant number of multiplications or divisions by a small integer. This is possible because in all algorithms the parameters of the binomial coefficients vary only by \(\pm 1\) from one step to the next. For instance, in Algorithm 2, just before incrementing \(i\) on Line 9, the coefficient for the _next_ iteration can be obtained by multiplying \(b\) by \(k-1-i\) and dividing it by \(n-1-m-i\). Similarly, in the other branch of the if, just before incrementing \(m\) on Line 12, the value of the coefficient for the next iteration can be obtained by multiplying \(b\) by \(n-m-k\) and dividing it by \(n-1-m-i\). In the end, only the first binomial coefficient is computed from scratch and all others are obtained as described above. This lowers the amortized cost of computing one coefficient to \(\Theta(1)\) multiplication of a big integer by a small integer. This optimization is applicable to all the algorithms presented in this paper. In Algorithm 6, we propose an optimized version of our Algorithm 2 based on the above remarks. It also includes some other enhancements. First, instead of computing the permutation rank of the combination and then unranking the combination as a permutation, it is possible to process the coefficients of the factoradic decomposition on the fly to extract the right value from the set \(\{0,1,2,\ldots,n-1\}\). Second, we can note that we are in a special use-case of the Extract function where values are extracted in increasing order. Hence, there is no need to explicitly store the set of remaining values (not yet in the combination) to get access to its \(m\)th value: it is \(m+i\) where \(i\) is the number of already extracted values. Finally, the last component of the combination can be deduced without computing more binomial coefficients (Line 15) in order to leave the loop earlier. Before going on with the efficiency comparisons, we use the remarks related to the binomial coefficient computation to improve Algorithms 3-5. Furthermore, to make the comparison fair, we used a variant of Algorithm 3 for the recursive approach in which the array storing the result is allocated with the right size at the beginning of the execution, as in the other algorithms. In addition, in order not to penalize it due to its recursive nature, the order of some instructions have been changed so that it is tail-recursive. The optimized version is given in Algorithm 7. In UnrankTR, the variable \(i\) represents the position in \(L\) of the next value to be computed and the variable \(m\) represents the next candidate to be the value of \(L[i]\). The invariant satisfied by \(b\) is that UnrankTR is always called with \(b=n\cdot(n-1)\). We propose a second time efficiency comparison for some algorithms with their optimizations in Figure 2. Comparing this plot with the leftmost one of Figure 1, we note that, when \(n=10{,}000\), the algorithms run approximately 45 times faster. Again, we note that Algorithm 5 is still less efficient than the others, which all seem to be equivalent.