\ifx\endpart\undefined
\input macros.tex
\fi

\chapter{Ranking Combinatorial Structures}

\section{Ranking and unranking}

The techniques for building efficient data structures on the RAM described
in Chapter~\ref{ramchap} can be also used for a~variety of problems related
to ranking of combinatorial structures. Generally, the problems are stated
in the following way:

\defn\id{rankdef}%
Let~$C$ be a~set of objects and~$\prec$ a~linear order on~$C$. The \df{rank}
$R_{C,\prec}(x)$ of an~element $x\in C$ is the number of elements $y\in C$ such that $y\prec x$.
When~$\prec$ is defined on some superset of~$C$, we naturally extend the rank
to elements outside~$C$.
We will call the function $R_{C,\prec}$ the \df{ranking function} for $C$ and~$\prec$
and its inverse $R^{-1}_{C,\prec}$ the \df{unranking function}. When the set
and the order are clear from the context, we will use just~$R(x)$ and $R^{-1}(x)$.

\example
Let us consider the set $C_k=\{\0,\1\}^k$ of all binary strings of length~$k$ ordered
lexicographically. Then $R^{-1}(i)$ is the $i$-th smallest element of this set, that
is the number~$i$ written in binary and padded to~$k$ digits (i.e., $\(i)_k$ in the
notation of Section~\ref{bitsect}). Obviously, $R(x)$ is the integer whose binary
representation is~$x$.

\FIXME{Uses of ranks.}

\para
In this chapter, we will investigate how to compute the ranking and unranking
functions on different sets. Usually, we will make use of the fact that the ranks
(and hence the input and output of our algorithm) are large numbers, so we can
use the integers of a~similar magnitude to represent non-trivial data structures.
This will allow us to design efficient algorithms on the RAM.

\FIXME{In the whole chapter, assume RAM.}

\section{Ranking of permutations}

\endpart
