Ranking and unranking functions

This article page is a stub, please help by expanding it.

---

The following definitions are from Kreher & Stinson:

A ranking algorithm determines the position (or rank) of a combinatorial object among all the objects (with respect to a given order); an unranking algorithm finds the object having a specified rank. Thus, ranking and unranking can be considered as inverse operations.

Here are slightly more formal mathematical descriptions of these concepts. Suppose that $\scriptstyle S$ is a finite set and $\scriptstyle N=|S|$. A ranking function will be a bijection

$\scriptstyle rank~:~S~\rightarrow ~{0,\dots ,N-1}$.

A rank function defines a total ordering on the elements of $\scriptstyle S$, by the obvious rule

$\scriptstyle s~<~t~\iff ~rank(s)~<~rank(t)$.

Conversely, there is a unique rank function associated with any total ordering defined on $\scriptstyle S$.

If rank is a ranking function defined on $\scriptstyle S$, then there is a unique unranking function associated with the function rank. This function unrank is also a bijection,

$\scriptstyle unrank~:~{0,\dots ,N-1}~\rightarrow ~S$.

unrank is the inverse function of the function rank, i.e., we have

$\scriptstyle rank(s)~=~i~\iff ~unrank(i)~=~s$,

for all $\scriptstyle s~\in ~S$ and all $\scriptstyle i~\in ~{0,\dots ,N-1}$.

For a shorter formal definition, see

Local rank vs. Global rank

Above definitions presuppose that there is a only finitely many combinatorial objects (or structures) in the set $\scriptstyle S$. This is true when we consider, for example, the object's position in the finite subset of objects of the same size. This is what the author (AK) of this page calls a Local rank. However, if we are interested about the combinatorial object's position among the whole infinite ensemble of the said combinatorial structures (which includes all sizes), then we have to, (for example), add the partial sum of counts of smaller objects to the local rank, to get what the author of this page calls a Global rank. Formally, we have:

$\scriptstyle Grank(s)~=~Lrank(s)~+\sum _{n=0}^{size(s)-1}\,count(n)\,$

where $\scriptstyle size(s)$ gives the size of the combinatiorial structure $\scriptstyle s$ and $\scriptstyle count(n)$ gives the number of similar combinatorial structures of size $\scriptstyle n$.

Similarly, the Global unranking function can be computed with the help of Local unranking function as:

$\scriptstyle Gunrank(i)~=~Lunrank(size,i-\sum _{n=0}^{size-1}\,count(n))\,$

where $\scriptstyle size$ has been computed with the help of auxiliary function $\scriptstyle {Grank}\rightarrow {size}$ as

$\scriptstyle size~=~{Grank}\rightarrow {size}(i)~=~the~smallest~integer~k~for~which~\sum _{n=0}^{k}\,count(n)~\geq ~i+1\,$

thus $\scriptstyle {Grank}\rightarrow {size}(i)$, for $\scriptstyle i=0..\infty$ will result a monotone (i.e. non-decreasing) integer sequence where each non-negative integer $\scriptstyle i$ occurs $\scriptstyle count(i)$ times in succession:

$\scriptstyle \{count(0)\times 0,~count(1)\times 1,~count(2)\times 2,~\dots \}$.

Note that the above definition of $\scriptstyle Lunrank$ contains the argument $\scriptstyle size$ explicitly in its parameter list, in contrast to the definition of unrank as given by Kreher & Stinson where the result is implicitly assumed to depend on it.

Now we see that a global ranking function is a bijection from the whole enumerable set $\scriptstyle S$ of the said combinatorial structures to nonnegative integers $\scriptstyle \mathbb {N} _{0}\,=\,\{0,1,2,3,...\}$ :

$\scriptstyle Grank~:~S~\rightarrow ~{0,1,2,3,\dots }$

and conversely, a global unranking function is its inverse (i.e. $\scriptstyle Grank(s)~=~i~\iff ~Gunrank(i)~=~s$), a bijection from non-negative integers to the combinatorial structures in question:

$\scriptstyle Gunrank~:~\mathbb {N} _{0}~\rightarrow ~S$.

Sometimes, any pair of such functions, of which the other function is a bijection between the enumerable set $\scriptstyle S$ and nonnegative integers, and the other its inverse, are called (global) ranking and unranking functions for the combinatorial structures in question, even if they would not respect any order based on conspicuous criteria, like e.g. lexicographic ordering or any of its variants or even a size-wise ordering of the elements in $\scriptstyle S$. See for example Alternative Catalan Orderings.

Ranking and unranking functions for specific combinatorial structures

In general, it's always possible to use the above scheme for constructing ranking and unranking functions for any enumerable combinatorial structure which has at least one parameter (usually the structure's "size", e.g. a number of vertices, edges, elements, etc.) that grows without limit from zero (or one) onward, but which nevertheless gets only finite number of times any particular finite value. However, in some cases shortcuts are possible.

Ranking and unranking functions for Catalan objects

When ranking and unranking (i.e. generating) Catalan objects, it's fortunate that many combinatorial interpretations of Catalan numbers allow an easy and unambiguous encoding as nonnegative integers, thus the set $\scriptstyle S\,$ in above definitions will actually be a subset of $\scriptstyle N_{0}\,$, and functions like $\scriptstyle Gunrank\,$ for those interpretations can be represented as integer sequences. The most obvious integer encoding for many Catalan interpretations uses totally balanced binary sequences, which consists of following binary strings

{{10}, {1010, 1100}, {101010, 101100, 110010, 110100, 111000}, {10101010, 10101100, 10110010, 10110100, 10111000, 11001010, 11001100, 11010010, 11010100, 11011000, 11100010, 11100100, 11101000, 11110000}, ...}

where in the $\scriptstyle n$th subsequence there are A000108($\scriptstyle n$) binary sequences, each of length $\scriptstyle 2n\,$.

In this case, the (local) unranking function $\scriptstyle Lunrank(size,lrank)\,$ is given by the array A213704, and considered as a dyadic function A213704bi(size,lrank) it gives the $\scriptstyle lrank$th such balanced binary string of $\scriptstyle 2\times size\,$ bits, converted to decimal.

The auxiliary function $\scriptstyle {Grank}\rightarrow {size}(i)\,$ is in this case a function that returns the smallest integer $\scriptstyle k\,$ such that $\scriptstyle \sum _{n=0}^{k}\,C(n)~\geq ~i+1\,$, where $\scriptstyle C(n)\,$ means the nth Catalan number, A000108(n), that is, the smallest integer $\scriptstyle k\,$ for which A014137(k) $\scriptstyle ~\geq ~i+1\,$.

This gives us the sequence A072643, where each $\scriptstyle n\,$ occurs $\scriptstyle A000108(n)\,$ times:

{0, 1, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, ...}

Now, setting $\scriptstyle size~=~{Grank}\rightarrow {size}(i)~=~A072643(i)\,$ means that the global unranking function $\scriptstyle Gunrank(i)~=~Lunrank(size,i-\sum _{n=0}^{size-1}\,count(n))\,$ can be obtained with a function Gunrank(i) = A213704bi(A072643(i),(i - A014137(A072643(i)-1))). This function has been submitted as the sequence A014486 into OEIS.

For ranking totally balanced binary sequences, one uses the local ranking function A080301 and the global ranking ranking function A080300 (or A215406).

The implementations of Catalan ranking and unranking functions in various programming languages can be found at separate source code for Catalan ranking and unranking functions -page.

Authorship

The first version of this page was written by Antti Karttunen Aug 8-9, 2012.

Cite this page as

A. Karttunen et al., <a href="http://oeis.org/wiki/Ranking_and_unranking_functions">Ranking_and_unranking_functions</a>, OEIS Wiki.