# Unranking Small Combinations of a Large Set in Co-Lexicographic Order
## 2 Materials and Methods  
### Algorithms for Ranking and Unranking Combinations in Co-Lexicographic Order  
There are several variants for ordering any list of strings or sequences, for example, the well-known lexicographic and co-lexicographic orders [2]. Lexicographic (lex) order is a such order in which \(a_{1},a_{2},\ldots,a_{n}<b_{1},b_{2},\ldots,b_{m}\) if \(n=m\) and there exists \(k\in\{1,\ldots,n\}\) satisfying \(a_{k}<b_{k}\) and \(a_{i}=b_{i}\) for every \(i<k\) or if \(n<m\) and \(a_{i}=b_{i}\) for \(i\leq n\). Co-lexicographic (colex) order is a such order in which \(a_{1},a_{2},\ldots,a_{n}<b_{1},b_{2},\ldots,b_{m}\) if \(a_{1},\ldots,a_{2},a_{1}<b_{m},\ldots,b_{2},b_{1}\) in lex order.  
Lex order is a natural and clear way of ordering. At the same time, colex order can make combinatorial algorithms shorter, faster, more elegant and natural [4]. For ranking a combination \(c=(c_{1},c_{2},\ldots,c_{m})\) in colex order, we can use the next formula (Equation (4.10) in [4]):  
\[\mathtt{RankColex}(c)=\sum_{i=1}^{m}\binom{c_{i}-1}{i}. \tag{1}\]  
Applying (1), it is possible to calculate the rank of a given \(m\)-combination of an \(n\)-set fast, even for large \(n\) since it is independent of \(n\). Let us consider the following algorithm for unranking combinations in colex order (Algorithm 4.10 in [4]):  
For a given \(m\)-combination of an \(n\)-set, Algorithm 1 takes the number \(m\) of the selected elements and the rank \(r<\binom{n}{m}\) of the combination in colex order as input. As a result, the values of the selected elements \(c_{i}\) in the combination will be obtained in the form of a sequence \((c_{1},c_{2},\ldots,c_{m})\). The main idea of this algorithm for unranking combinations in colex order is as follows. First, for the case \(k=m\), we search for the interval that contains the rank \(r\) among the following binomial coefficients:  
\[\binom{m}{m}+\binom{m+1}{m}+\binom{m+2}{m}+\ldots+\binom{n}{m}=\binom{n+1}{m +1}. \tag{2}\]  
```
algorithm: UnrankColex(\(r\),\(m\)) input: A nonnegative integer \(m\) and a rank \(r\) output: A sequence \(c=(c_{1},c_{2},\ldots,c_{m})\) begin for\(i:=m\)to\(1\)do \(k:=i\) while\(r\geq\binom{k}{i}\)do\(k:=k+1\) \(c_{i}:=k\) \(r:=r-\binom{k-1}{i}\) end for return\(c\)  end for
```  
**Algorithm 1**Algorithm for unranking combinations in colex order  
It is easy to see that the number of terms on the left in (2) is \(n-m+1\). If we know the rank \(r\) of an \(m\)-combination of an \(n\)-set and the solution for  
\[\binom{k-1}{m}\leq r<\binom{k}{m}, \tag{3}\]  
then the \(m\)-th selected element in the combination is equal to \(k\). Next, we need to get the \((m-1)\)-th selected element in the combination by searching for the interval that contains the rank  
\[r:=r-\binom{k-1}{m}. \tag{4}\]  
Thus, solving (3) and applying (4), we can sequentially find the values of the selected elements of the \(m\)-combination with the rank \(r\). For \(m<n-m\), the computational complexity of Algorithm 1 is \(O\big{(}m^{2}\cdot(n-m)\big{)}\) which was obtained on the basis of the following information:  
* the number of iterations in the for-loop (Line 2 in Algorithm 1) is \(m\);
* the minimum number of comparisons in the while-loop (Line 4 in Algorithm 1) is \(n-m+1\) (when \(i=m\)) and the maximum number of comparisons is \(n\) (when \(i=1\));
* the computational complexity of calculating the value of a binomial coefficient \(\binom{n}{m}\) is \(O(m)\) when \(m<n-m\) and \(O(n-m)\) when \(m>n-m\).  
For large \(n\) and small \(m\), the number of intervals in (3) that can contain the required rank \(r\) is large due to the dependence on \(n\). The goal of our improvements of Algorithm 1 is to reduce the number of comparisons in the while-loop (Line 4 in Algorithm 1). For this purpose we need to find the solution of (3) fast.