# Lexographic Unranking of Combinations Revisited
## 2 Unranking through Factoradics: A New Strategy
### Link between the Factorial Number System and Permutations  
We recall that the factorial number system, or factoradics, is a mixed radix numeral system in which the representation of integers relies on the use of factorial numbers. Its definition belongs to the folklore but already appeared in 1888 in [17].  
**Definition 4**.: _Let \(u\) be a positive integer and let \(n\) be the unique integer satisfying \((n-1)!\leq u<n!\). Then, there exists a unique sequence of integers \((f_{\ell})_{\ell\in\{0,\dots,n-1\}}\), with \(0\leq f_{\ell}\leq\ell\) for all \(\ell\), such that:_  
\[u=f_{0}\cdot 0!+f_{1}\cdot 1!+\dots+f_{n-2}\cdot(n-2)!+f_{n-1}\cdot(n-1)!\]  
_The finite sequence \((f_{0},f_{1},\dots,f_{n-1})\) is called the factoradic decomposition (or factoradic) of \(u\) (note that \(f_{0}=0\) for all \(u\))._  
Taking the number \(\mathbf{u}=2021\) as an example, we obtain the following decomposition: \(2021=0\times 0!+1\times 1!+2\times 2!+0\times 3!+4\times 4!+4\times 5!+2 \times 6!\). Thus, its factoradic is \((0,1,2,0,4,4,2)\).  
**Definition 5**.: _Let \(n\) be a positive integer. A permutation of size \(n\) is an ordering of the elements of the set \(\{0,1,\dots,n-1\}\)._  
We represent a permutation of size \(n\) as a finite sequence of length \(n\) indicating the order of its elements. For example, the sequence \((2,4,0,3,1)\) is a permutation of size \(5\).  
The factorial number system is particularly suitable to define a one-to-one correspondence between integers and permutations and thus can be used as an unranking method for permutations. The algorithm implemented in the function UnrankingPermutation in Algorithm 1 is a straightforward adaptation of the Fisher-Yates random sampler for permutations [18].  
**Fact 1**.: _For all \(0\leq u<n!\), UnrankingPermutation\((n,u)\) returns the \(u\)th permutation in lexicographic order among the \(n!\) permutations of \(n\) elements._  
```
1:functionUnrankingPermutation(\(n,u\))
2:\(F\leftarrow\texttt{factoradic}(u)\)
3:while\(\texttt{length}(F)<n\)do
4:\(\texttt{append}(F,0)\)
5:return\(\texttt{Extract}(F,n,n)\)
```  
**factoradic(\(u\))**: computes the factoradic of \(u\);  
\(\texttt{length}(F)\): computes the number of components in \(F\);  
\(\texttt{append}(F,i)\): appends the element \(i\) at the end of \(F\);  
\(\texttt{remove}(F,i)\): removes from \(F\) the element at index \(i\). ```
**Algorithm 1** Unranking a permutation.  
Since the factoradic (with 8 components) of 2021 is \((0,1,2,0,4,4,2,0)\), the permutation (of size 8) of rank 2021 is \((0,3,6,7,1,5,4,2)\). To obtain this permutation, we read the factoradic from right to left, and extract iteratively from the list \((0,1,\dots,8-1)\) the element whose index is the coefficient read in the factoradic. This goes on until the list is empty and we reach the leftmost component of the factoradic. Thus, in our example, we start by extracting the element of index 0, which is 0. Then, the list \(P\) becomes \((1,2,\dots,7)\) and we extract the element of index 2, which is 3. Then, \(P\) becomes \((1,2,4,5,6,7)\) and we extract the fourth element, which is 6, and so on.  
Note that, for the sake of clarity, we present the function Extract using a list for \(P\), but a better data structure must be used to achieve good performance. Good candidatesare dynamic balanced trees, as presented in [19], or multisets with elements of weight 1 or 0, as presented in the Appendix of [20], since both provide logarithmic access and removal. Unfortunately, it seems that there is no algorithm based on some swap operation giving an in-place shuffle to unrank permutations in the lexicographic order; put differently: [PERSON]'s algorithm [21] cannot be easily adapted for the lexicographic order.