rank.tex

   1 \ifx\endpart\undefined
   2 \input macros.tex
   3 \fi
   4
   5 \chapter{Ranking Combinatorial Structures}
   6
   7 \section{Ranking and unranking}
   8
   9 The techniques for building efficient data structures on the RAM described
  10 in Chapter~\ref{ramchap} can be also used for a~variety of problems related
  11 to ranking of combinatorial structures. Generally, the problems are stated
  12 in the following way:
  13
  14 \defn\id{rankdef}%
  15 Let~$C$ be a~set of objects and~$\prec$ a~linear order on~$C$. The \df{rank}
  16 $R_{C,\prec}(x)$ of an~element $x\in C$ is the number of elements $y\in C$ such that $y\prec x$.
  17 When~$\prec$ is defined on some superset of~$C$, we naturally extend the rank
  18 to elements outside~$C$.
  19 We will call the function $R_{C,\prec}$ the \df{ranking function} for $C$ and~$\prec$
  20 and its inverse $R^{-1}_{C,\prec}$ the \df{unranking function}. When the set
  21 and the order are clear from the context, we will use just~$R(x)$ and $R^{-1}(x)$.
  22
  23 \example
  24 Let us consider the set $C_k=\{\0,\1\}^k$ of all binary strings of length~$k$ ordered
  25 lexicographically. Then $R^{-1}(i)$ is the $i$-th smallest element of this set, that
  26 is the number~$i$ written in binary and padded to~$k$ digits (i.e., $\(i)_k$ in the
  27 notation of Section~\ref{bitsect}). Obviously, $R(x)$ is the integer whose binary
  28 representation is~$x$.
  29
  30 \FIXME{Uses of ranks.}
  31
  32 \para
  33 In this chapter, we will investigate how to compute the ranking and unranking
  34 functions on different sets. Usually, we will make use of the fact that the ranks
  35 (and hence the input and output of our algorithm) are large numbers, so we can
  36 use the integers of a~similar magnitude to represent non-trivial data structures.
  37 This will allow us to design efficient algorithms on the RAM.
  38
  39 \FIXME{In the whole chapter, assume RAM.}
  40
  41 \section{Ranking of permutations}
  42
  43 \endpart