# Unranking Small Combinations of a Large Set in Co-Lexicographic Order
## 3 Results  
We have performed a computational experiment for checking the obtained Formula (11). For this purpose we set the number of selected elements \(m\) in the range of 10 to 200 and the rank \(r\) in the range of \(10^{100}\) to \(10^{200}\). For these values of \(m\) and \(r\), we have the distribution of values of \(n\) in the range of 332 (when \(m=170\) and \(r=10^{100}\)) to \(4.5*10^{20}\) (when \(m=10\) and \(r=10^{200}\)). Then we calculate the difference between the value of \(k\) obtained by using the approximate Formula (11) and the value of \(k\) obtained by using the while-loop (Line 4 in Algorithm 1). The results of the computational experiment are presented in Table 1.  
From Table 1 we can see that the errors are small. Note that increasing \(r\) reduces the errors, but increasing \(m\) raises the errors. It is explained by the use of the approximate Formulas (8) and (10) for calculations. Moreover, we can not use the approximate Formula (11) for small \(m\) because the application of (10) to such values of \(m\) leads to an increase in errors. Therefore, for small \(m\) we can find the values of \(k\) by solving an equation obtained from (9):  
\begin{table}
\begin{tabular}{c c c c c c c c c c c c} \hline \hline \(m\) & \(r\) & \(10^{100}\) & \(10^{100}\) & \(10^{100}\) & \(10^{100}\) & \(10^{100}\) & \(10^{100}\) & \(10^{100}\) & \(10^{100}\) & \(10^{100}\) \\ \hline
10 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\
20 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\
30 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
40 & 0 & 0 & 0 If \(m=1\), then we get  
\[r<\binom{k}{1}.\]  
In this case, we can use the following initial condition for the value of \(k\):  
\[k=r.\]  
If \(m=2\), then we get  
\[r<\binom{k}{2}\]  
or  
\[k^{2}-k-2r>0.\]  
In this case, we can use the following initial condition for the value of \(k\):  
\[k=\left\lceil\frac{1+\sqrt{1+8r}}{2}\right\rceil.\]  
For other small values of \(m\) we can use other approximate formulas for solving (9), for example, it can be the approximate Formula (8). Hence, we obtain an algorithm for preliminary search for the values of \(k\) (Algorithm 3). In this algorithm, the parameter \(s\) shows the boundary value of \(m\) for applying the approximate Formula (11). ```
algorithm: FindK(\(r\),\(m\)) input: A nonnegative integer \(m\) and a rank \(r\) output: A nonnegative integer \(k\)
1 begin
2 if\(r=0\)then\(k:=m\)
3 elseif\(m=1\)then\(k:=r\)
4 elseif\(m=2\)then\(k:=\left\lceil\frac{1+\sqrt{1+8r}}{2}\right\rceil\)
5 elseif\(m<s\)then\(k:=k\approx\left\lceil\sqrt[n]{r\;m! }+\frac{m-1}{2}\right\rceil\)
6 else\(k:=\left\lceil m\;e^{\frac{\log r}{m}+\frac{\log m}{2m}+\frac{1}{12m^{2}}- \frac{1}{360m^{4}}-1}+\frac{m-1}{2}\right\rceil\)
7 return\(k\)
8 end if
```  
**Algorithm 3**Preliminary search for the values of \(k\) for Algorithm 2  
Algorithm 2 with the use of Algorithm 3 has \(O(m\cdot(m+\varepsilon m))\approx O(m^{2})\) time complexity (assuming algebraic operations with numbers in \(O(1)\)). This is determined by the number \(m\) of iterations in the for-loop (Line 2 in Algorithm 2) where each loop requires:  
* preliminary search for the value of \(k\) (Line 3 in Algorithm 2) by using Algorithm 3 that has \(O(m)\) time complexity;
* search for the true value of \(k\) by making \(\varepsilon\) iterations in the while-loop (Line 4 in Algorithm 2);
* calculation of the value of a binomial coefficient \(\binom{n}{m}\) that has \(O(m)\) time complexity when \(m<n-m\). The parameter \(\varepsilon\) is the error in determining the value of \(k\) that is substantially smaller than \(n\) (see Table 1). Hence, the modified Algorithm 2 has the polynomial complexity that depends only on \(m\). In the case when \(n\) is large and \(m\) is small, this algorithm will be better than the original Algorithm 1 due to the independence of \(n\) in its complexity. We have also performed a computational experiment aimed at comparing the obtained algorithm for unranking small combinations of a large set in colex order with [PERSON]'s unranking algorithm [30; 31].