# Lexographic Unranking of Combinations Revisited
## 2 Unranking through Factoradics: A New Strategy
### Combinations Unranking through Factoradics  
We start with the definition of our algorithm to unrank _combinations_ via the use of factoradics. The basic ideas driving our algorithm are the following:  
1. We define a bijection between the combinations of \(k\) elements among \(n\) and a subset of the permutations of \(n\) elements. 2. We transform the combination rank \(u\) into the rank \(u^{\prime}\) of the appropriate permutation. 3. We build (the prefix of) the permutation of rank \(u^{\prime}\) by using Algorithm 1. **Definition 6**. : _Let \(n\) and \(k\) be two integers with \(0\leq k\leq n\). We define \(\mathcal{P}_{n,k}\) as the function which maps the combination \((\ell_{0},\ell_{1},\ldots,\ell_{k-1})\) to the size-\(n\) permutation \((\ell_{0},\ell_{1},\ldots,\ell_{k-1},d_{k},\ldots,d_{n-1})\) where the integers \(d_{i}\) are such that \(d_{k}<d_{k+1}<\cdots<d_{n-1}\) and \(\{\ell_{0},\ldots,\ell_{k-1},d_{k},\ldots,d_{n-1}\}=\{0,1,\ldots,n-1\}\)._  
For instance, by definition, for \(n=5\) and \(k=3\), the permutations associated with the combinations \((0,1,2)\) and \((0,2,4)\) are, respectively, \((0,1,2,3,4)\) and \((0,2,4,1,3)\). Note that the function \(\mathcal{P}_{n,k}\) returns the smallest size-\(n\) permutation for the lexicographic order whose prefix is the given combination. **Proposition 1**. : _For all integers \(0\leq k\leq n\), the function \(\mathcal{P}_{n,k}\) is a bijection from the set of \((n,k)\) combinations to the set of size-\(n\) permutations whose prefix of length \(k\) and suffix of length \(n-k\) are both increasingly sorted._  
Remark that the permutation (of size 5) \((0,1,2,3,4)\) is the permutation associated with combinations \((0,1)\) and \((0,1,2)\) by, respectively, \(\mathcal{P}_{2,5}\) and \(\mathcal{P}_{3,5}\). In fact, there are exactly six combinations associated with the latter permutation, but for different values of \(k\). The proof of Proposition 1 is straightforward. **Fact 2**. : _For any integer \(m\geq 0\), the number of sequences \((f_{i})_{0\leq i<n}\) satisfying \(n-k\geq f_{n-k}\geq f_{n-k+1}\geq\cdots\geq f_{n-1}\geq m\) is given by \(\binom{n-m}{k}\)._  
In fact, we get this result using a classical cardinality argument: a sequence of integers of the form \(x_{0}=0\leq x_{1}\leq x_{2}\leq\cdots\leq x_{k}\leq x_{k+1}=\ell\) corresponds to a weak composition (consider the differences \(x_{i+1}-x_{i}\)) of the integer \(\ell\) into \(k+1\) terms. The number of such compositions is given by \(\binom{\ell+k}{k}\). Hence, the number of sequences matching the description of Fact 2 is given by \(\binom{n-k-m+k}{k}\). We now exhibit how to transform a combination rank into its corresponding permutation rank. **Lemma 1**. : _For any given \(0\leq k\leq n\), the factoradic decompositions of the ranks of the permutations obtained as the image by \(\mathcal{P}_{n,k}\) of some combination of \(k\) elements among \(n\) are all the finite sequences of the form \((0,\ldots,0,f_{n-k},\ldots,f_{n-1})\) with \(n-k\geq f_{n-k}\geq f_{n-k+1}\geq\cdots\geq f_{n-1}\geq 0\)._  
Proof. : Let \(u\) be an integer whose factoradic is \((0,\ldots,0,f_{n-k},\ldots f_{n-1})\) as in the lemma. Due to the constraint \(n-k\geq f_{n-k}\geq f_{n-k+1}\geq\cdots\geq f_{n-1}\geq 0\), the permutation corresponding to \(u\) has for prefix of length \(k\) the sequence \((f_{n-1},f_{n-2}+1,f_{n-3}+2,\ldots,f_{n-k}+k-1)\) which is increasingly sorted. The rest of the permutation (the suffix of length \(n-k\)) corresponds to the increasing sequence of elements that have not been taken yet. Thus, the result correspondsto a combination via \(\mathcal{P}_{n,k}\). Fact 2 completes the proof. Thus, to convert the combination rank \(u\) into its corresponding permutation rank \(u^{\prime}\), it is sufficient to find the \(u\)th sequence satisfying Lemma 1 in _co-lexicographic order_. This is presented in Algorithm 2 where the RankConversion function implements the conversion from \(u\) to \(u^{\prime}\) and the UnrankingCombination function implements the whole unranking procedure.