\fi
\chapter{Ranking Combinatorial Structures}
+\id{rankchap}
-\section{Ranking and unranking}
+\section{Ranking and unranking}\id{ranksect}%
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
\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)$.
+We will call the function $R_{C,\prec}$ the \df{ranking function} for $C$ ordered by~$\prec$
+and its inverse $R^{-1}_{C,\prec}$ the \df{unranking function} for $C$ and~$\prec$. When the set
+and the order are clear from the context, we will use plain~$R(x)$ and $R^{-1}(x)$.
+Also, when $\prec$ is defined on a~superset~$C'$ of~$C$, we naturally extend $R_C(x)$
+to elements $x\in C'\setminus C$.
\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$.
+representation is the string~$x$.
\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.
+functions for different sets efficiently. 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.
-\FIXME{We will assume RAM in the whole chapter.}
+\para
+Until the end of the chapter, we will always assume that our model of computation
+is the Random Access Machine (more specifically, the Word-RAM).
+
+%--------------------------------------------------------------------------------
\section{Ranking of permutations}
\id{pranksect}
most cases, the time complexity of the whole algorithm is limited by the efficiency
of the (un)ranking functions.
-In most cases, the permutations are ranked according to their lexicographic order.
+The permutations are usually ranked according to their lexicographic order.
In fact, an~arbitrary order is often sufficient if the ranks are used solely
-for indexing of arrays, but the lexicographic order has an~additional advantage
-of a~nice structure allowing many additional operations on permutations to be
+for indexing of arrays. The lexicographic order however has an~additional advantage
+of a~nice structure, which allows various operations on permutations to be
performed directly on their ranks.
Na\"\i{}ve algorithms for lexicographic ranking require time $\Theta(n^2)$ in the
(un)ranking.
\nota\id{brackets}%
-We will view permutations on a~ordered set~$A\subseteq {\bb N}$ as ordered $\vert A\vert$-tuples
+We will view permutations on a~finite set $A\subseteq {\bb N}$ as ordered $\vert A\vert$-tuples
(in other words, arrays) containing every element of~$A$ exactly once. We will
-use square brackets for indexing of these tuples: $\pi=(\pi[1],\ldots,\pi[\vert A\vert])$.
-The corresponding lexicographic ranking and unranking functions will be denoted by~$L(\pi,A)$
-and $L^{-1}(i,A)$ respectively.
+use square brackets to index these tuples: $\pi=(\pi[1],\ldots,\pi[\vert A\vert])$,
+and sub-tuples: $\pi[i\ldots j] = (\pi[i],\ldots,\pi[j])$.
+The lexicographic ranking and unranking functions for the permutations on~$A$
+will be denoted by~$L(\pi,A)$ and $L^{-1}(i,A)$ respectively.
-\obs
+\obs\id{permrec}%
Let us first observe that permutations have a simple recursive structure.
If we fix the first element $\pi[1]$ of a~permutation~$\pi$ on the set~$[n]$, the
elements $\pi[2], \ldots, \pi[n]$ form a~permutation on $[n]-\{\pi[1]\} = \{1,\ldots,\pi[1]-1,\pi[1]+1,\ldots,n\}$.
The lexicographic order of two permutations $\pi$ and~$\pi'$ on the original set is then determined
by $\pi[1]$ and $\pi'[1]$ and only if these elements are equal, it is decided
-by the lexicographic comparison of permutations $(\pi[2],\ldots,\pi[n])$ and
-$(\pi'[2],\ldots,\pi'[n])$. Therefore the rank of $\pi$ is $(\pi[1]-1)\cdot
-(n-1)!$ plus the rank of $(\pi[2],\ldots,\pi[n])$.
+by the lexicographic comparison of permutations $\pi[2\ldots n]$ and $\pi'[2\ldots n]$.
+Moreover, for fixed~$\pi[1]$ all permutations on the smaller set occur exactly
+once, so the rank of $\pi$ is $(\pi[1]-1)\cdot (n-1)!$ plus the rank of
+$\pi[2\ldots n]$.
-This gives us a~reduction from (un)ranking of permutations on $[n]$ to (un)ranking
+This gives us a~reduction from (un)ranking of permutations on $[n]$ to (un)rank\-ing
of permutations on a $(n-1)$-element set, which suggests a straightforward
algorithm, but unfortunately this set is different from $[n-1]$ and it even
depends on the value of~$\pi[1]$. We could renumber the elements to get $[n-1]$,
-but it would require linear time per iteration. Instead, we generalize the
+but it would require linear time per iteration. To avoid this, we generalize the
problem to permutations on subsets of $[n]$. For a permutation $\pi$ on a~set
$A\subseteq [n]$ of size~$m$, similar reasoning gives a~simple formula:
$$
L((\pi[1],\ldots,\pi[m]),A) = R_A(\pi[1]) \cdot (m-1)! +
L((\pi[2],\ldots,\pi[m]), A\setminus\{\pi[1]\}),
$$
-which uses the ranking function~$R_A$ for~$A$. This formula leads to the
-following algorithms (a~similar formulation can be found for example in~\cite{knuth:sas}):
+which uses the ranking function~$R_A$ for~$A$. This recursive formula immediately
+translates to the following recursive algorithms for both ranking and unranking
+(described for example in \cite{knuth:sas}):
-\alg $\<Rank>(\pi,i,n,A)$: compute the rank of a~permutation $\pi[i\ldots n]$ on~$A$.
+\alg $\<Rank>(\pi,i,n,A)$: Compute the rank of a~permutation $\pi[i\ldots n]$ on~$A$.
+\id{rankalg}
\algo
\:If $i\ge n$, return~0.
\:$a\=R_A(\pi[i])$.
\>We can call $\<Rank>(\pi,1,n,[n])$ for ranking on~$[n]$, i.e., to calculate
$L(\pi,[n])$.
-\alg $\<Unrank>(j,i,n,A)$: Fill $\pi[i,\ldots,n]$ with the $j$-th permutation on~$A$.
+\alg $\<Unrank>(j,i,n,A)$: Return an~array~$\pi$ such that $\pi[i\ldots n]$ is the $j$-th permutation on~$A$.
+\id{unrankalg}
\algo
-\:If $i>n$, return immediately.
-\:$a\=R^{-1}_A(\lfloor j/(n-i)! \rfloor)$.
-\:$\pi\=\<Unrank>(j\bmod (n-i)!,i+1,n,A\setminus \{a\})$.
-\:$\pi[i]\=a$.
+\:If $i>n$, return $(0,\ldots,0)$.
+\:$x\=R^{-1}_A(\lfloor j/(n-i)! \rfloor)$.
+\:$\pi\=\<Unrank>(j\bmod (n-i)!,i+1,n,A\setminus \{x\})$.
+\:$\pi[i]\=x$.
+\:Return~$\pi$.
\endalgo
-\>We can call $\<Unrank>(j,1,n,[n])$ for the unranking problem on~$[n]$, i.e., to get $L^{-1}(j,[n])$.
+\>We can call $\<Unrank>(j,1,n,[n])$ for the unranking problem on~$[n]$, i.e., to calculate $L^{-1}(j,[n])$.
\para
The most time-consuming parts of the above algorithms are of course operations
-on the set~$A$. If we use a~data structure of a~known time complexity, the complexity
+on the set~$A$. If we store~$A$ in a~data structure of a~known time complexity, the complexity
of the whole algorithm is easy to calculate:
\lemma\id{ranklemma}%
-Suppose that there is a~data structure maintaining a~subset of~$[n]$ under insertion
-and deletion of single elements and ranking and unranking of elements, all in time
-at most $t(n)$ per operation. Then lexicographic ranking and unranking of permutations
-can be performed in time $\O(n\cdot t(n))$.
+Suppose that there is a~data structure maintaining a~subset of~$[n]$ under a~sequence
+of deletions, which supports ranking and unranking of elements, and that
+the time complexity of a~single operation is at most~$t(n)$.
+Then lexicographic ranking and unranking of permutations can be performed in time $\O(n\cdot t(n))$.
\proof
Let us analyse the above algorithms. The depth of the recursion is~$n$ and in each
-nested invokation of the recursive procedure we perform a~constant number of operations.
-All of them are either trivial or factorials (which can be precomputed in~$\O(n)$ time)
+nested invocation of the recursive procedure we perform a~constant number of operations.
+All of them are either trivial, or calculations of factorials (which can be precomputed in~$\O(n)$ time),
or operations on the data structure.
\qed
to the classical algorithms based on inversion vectors, because at the time of processing~$\pi[i]$,
the value of $R_A(\pi[i])$ is exactly the number of elements forming inversions with~$\pi[i]$.
-If we relax the requirements on the data structure to allow ordering of elements
-dependent on the history of the structure (i.e., on the sequence of deletes performed
-so far), we can implement all three operations in time $\O(1)$. We store
-the values in an array and we also keep an inverse permutation. Ranking is done by direct
-indexing, unranking by indexing of the inverse permutation and deleting by swapping
-the element with the last element. We can observe that although it no longer
-gives the lexicographic order, the unranking function is still the inverse of the
-ranking function (the sequence of deletes from~$A$ is the same in both functions),
-so this leads to $\O(n)$-time ranking and unranking in a~non-lexicographic order.
-This order is the same as the one used by Myrvold and Ruskey in~\cite{myrvold:rank}.
-
-However, for our purposes we need to keep the same order on~$A$ over the whole
-course of the algorithm. We will make use of the representation of vectors
-by integers on the RAM as developed in Section~\ref{bitsect}, but first of
-all, we will note that the ranks are large numbers, so the word size of the machine
-has to be large as well for them to fit:
+\para
+To obtain linear time complexity, we will make use of the representation of
+vectors by integers on the RAM as developed in Section~\ref{bitsect}, but first
+of all, we will make sure that the ranks are large numbers, so the word size of the
+machine has to be large as well:
\obs
-$\log n! = \Theta(n\log n)$, therefore the word size~$W$ must be~$\Omega(n\log n)$.
+$\log n! = \Theta(n\log n)$, therefore the word size must be~$\Omega(n\log n)$.
\proof
We have $n^n \ge n! \ge \lfloor n/2\rfloor^{\lfloor n/2\rfloor}$, so $n\log n \ge \log n! \ge \lfloor n/2\rfloor\cdot\log \lfloor n/2\rfloor$.
\qed
-\thmn{Ranking of permutations \cite{mm:rank}} When we order the permutations
-on the set~$[n]$ lexicographically, both ranking and unranking can be performed on the
-RAM in time~$\O(n)$.
+\thmn{Lexicographic ranking of permutations \cite{mm:rank}}
+When we order the permutations on the set~$[n]$ lexicographically, both ranking
+and unranking can be performed on the RAM in time~$\O(n)$.
\proof
-We will store the elements of the set~$A$ as a~sorted vector. Each element has
-$\O(\log n)$ bits, so the whole vector requires $\O(n\log n)$ bits, which by the
+We will store the elements of the set~$A$ in a~sorted vector. Each element has
+$\O(\log n)$ bits, so the whole vector takes $\O(n\log n)$ bits, which by the
above observation fits in a~constant number of machine words. We know from
Algorithm~\ref{vecops} that ranks can be calculated in constant time in such
vectors and that insertions and deletions can be translated to ranks and
masking. Unranking, that is indexing of the vector, is masking alone.
-So we can apply the previous Lemma~\ref{ranklemma} with $t(n)=\O(1)$.
+So we can apply the previous Lemma \ref{ranklemma} with $t(n)=\O(1)$.
+\qed
+
+\rem
+We can also easily derive the non-lexicographic linear-time algorithm of Myrvold
+and Ruskey~\cite{myrvold:rank} from our algorithm. We will relax the requirements
+on the data structure to allow order of elements dependent on the history of the
+structure (i.e., on the sequence of deletes performed so far). We can observe that
+although the algorithm no longer gives the lexicographic ranks, the unranking function
+is still an~inverse of the ranking function, because the sequence of deletes
+from~$A$ is the same when both ranking and unranking.
+
+The implementation of the relaxed structure is straightforward. We store the set~$A$
+in an~array~$\alpha$ and use the order of the elements in~$\alpha$ determine the
+order on~$A$. We will also maintain an~``inverse'' array $\alpha^{-1}$ such that
+$\alpha[\alpha^{-1}[x]]=x$ for every~$x\in A$. Ranking and unranking can be performed
+by a~simple lookup in these arrays: $R_A(x)=\alpha^{-1}[x]$, $R^{-1}(i)=\alpha[i]$.
+When we want to delete an~element, we exchange it with the last element in the
+array~$\alpha$ and update~$\alpha^{-1}$ accordingly.
+
+
+%--------------------------------------------------------------------------------
+
+\section{Ranking of \iftoc $k$\else{\secitfont k\/}\fi-permutations}
+\id{kpranksect}
+
+The technique from the previous section can be also generalized to lexicographic ranking of
+\df{$k$-permutations,} that is of ordered $k$-tuples drawn from the set~$[n]$.
+There are $n^{\underline k} = n\cdot(n-1)\cdot\ldots\cdot(n-k+1)$
+such $k$-permutations and they have a~recursive structure similar to the one of
+the permutations. We will therefore use the same recursive scheme as before
+(algorithms \ref{rankalg} and \ref{unrankalg}), but we will modify the first step of both algorithms
+to stop after the first~$k$ iterations. We will also replace the number $(n-i)!$
+of permutations on the remaining elements by the number of $(k-i)$-permutations on the same elements,
+i.e., by $(n-i)^{\underline{k-i}}$. As $(n-i)^{\underline{k-i}} = (n-i) \cdot (n-i-1)^{\underline{k-i-1}}$,
+we can precalculate all these numbers in linear time.
+
+Unfortunately, the ranks of $k$-permutations can be much smaller, so we can no
+longer rely on the same data structure fitting in a constant number of word-sized integers.
+For example, if $k=1$, the ranks are $\O(\log n)$-bit numbers, but the data
+structure still requires $\Theta(n\log n)$ bits.
+
+We do a minor side step by remembering the complement of~$A$ instead, that is
+the set of the at most~$k$ elements we have already seen. We will call this set~$H$
+(because it describes the ``holes'' in~$A$). Let us prove that $\Omega(k\log n)$ bits
+are needed to represent the rank, so the vector representation of~$H$ fits in
+a~constant number of words.
+
+\lemma
+The number of $k$-permutations on~$[n]$ is $2^{\Omega(k\log n)}$.
+
+\proof
+We already know that there $n^{\underline k}$ such $k$-permutations. If $k\le n/2$,
+then every term in the product is $n/2$ or more, so $\log n^{\underline k} \ge
+k\cdot (\log n - 1)$. If $k\ge n/2$, then $n^{\underline k} \ge n^{\underline{\smash{n/2}}}$
+and $\log n^{\underline k} \ge (n/2)(\log n - 1) \ge (k/2)(\log n - 1)$.
+\qed
+
+\para
+It remains to show how to translate the operations on~$A$ to operations on~$H$,
+again stored as a~sorted vector~${\bf h}$. Insertion to~$A$ correspond to
+deletion from~$H$ and vice versa. The rank of any~$x\in[n]$ in~$A$ is $x$ minus
+the number of holes that are smaller than~$x$, therefore $R_A(x)=x-R_H(x)$.
+To calculate $R_H(x)$, we can again use the vector operation \<Rank> from Algorithm \ref{vecops},
+this time on the vector~$\bf h$.
+
+The only operation we cannot translate directly is unranking in~$A$. We will
+therefore define an~auxiliary vector~$\bf r$ of the same size as~$\bf h$
+containing the ranks of the holes: $r_i=R_A(h_i)=h_i-R_H(h_i)=h_i-i$.
+To find the $j$-th smallest element of~$A$, we locate the interval between
+holes to which this element belongs: the interval is bordered from below by
+a~hole~$h_i$ such that $i$ is the largest index satisfying~$r_i \le j$.
+In other words, $i=\<Rank>(r,j+1)-1$. Finding the right element in the interval
+is then easy: $R^{-1}_A(j) = h_i + 1 + j - r_i$.
+
+\example
+If $A=\{2,5,6\}$ and $n=8$, then ${\bf h}=(1,3,4,7,8)$ and ${\bf r}
+= (0,1,1,3,3)$. When we want to calculate $R^{-1}_A(2)$, we find $i=2$ and
+the wanted element is $h_2+1+2-r_2 = 4+1+2-1 = 6$.
+
+\para
+The vector~$\bf r$ can be updated in constant time whenever an~element is
+inserted to~$\bf h$. It is sufficient to shift the fields apart (we know
+that the position of the new element in~$\bf r$ is the same as in~$\bf h$),
+insert the new value using masking operations and decrease all higher fields
+by one in parallel by using a~single subtraction. Updates after deletions
+from~$\bf h$ are analogous.
+
+We have replaced all operations on~$A$ by the corresponding operations on the
+modified data structure, each of which works again in constant time. Therefore
+we have just proven the following theorem, which brings this section to
+a~happy ending:
+
+\thmn{Lexicographic ranking of $k$-permutations \cite{mm:rank}}
+When we order the $k$-per\-mu\-ta\-tions on the set~$[n]$ lexicographically, both
+ranking and unranking can be performed on the RAM in time~$\O(k)$.
+
+\proof
+We modify algorithms \ref{rankalg} and \ref{unrankalg} for $k$-permutations as
+shown at the beginning of this section. We use the vectors $\bf h$ and~$\bf r$
+described above as an~implicit representation of the set~$A$. The modified
+algorithm uses recursion $k$~levels deep and as each operation on~$A$ can be
+performed in~$\O(1)$ time using $\bf h$ and~$\bf r$, every level takes only
+constant time. The time bound follows. \qed
+
+%--------------------------------------------------------------------------------
+
+\section{Restricted permutations}
+
+Another interesting class of combinatorial objects that can be counted and
+ranked are restricted permutations. An~archetypal member of this class are
+permutations without a~fixed point, i.e., permutations~$\pi$ such that $\pi(i)\ne i$
+for all~$i$. These are also called \df{derangements} or \df{hatcheck permutations.}\foot{%
+As the story in~\cite{matnes:idm} goes, once upon a~time there was a~hatcheck lady who
+was so confused that she was giving out the hats completely randomly. What is
+the probability that none of the gentlemen receives his own hat?} We will present
+a~general (un)ranking method for any class of restricted permutations and
+derive a~linear-time algorithm for the derangements from it.
+
+\defn\id{permnota}%
+We will fix a~non-negative integer~$n$ and use ${\cal P}$ for the set of
+all~permutations on~$[n]$.
+A~\df{restriction graph} is a~bipartite graph~$G$ whose parts are two copies
+of the set~$[n]$. A~permutation $\pi\in{\cal P}$ satisfies the restrictions
+if $(i,\pi(i))$ is an~edge of~$G$ for every~$i$.
+
+We will follow the path unthreaded by Kaplansky and Riordan
+\cite{kaplansky:rooks} and charted by Stanley in \cite{stanley:econe}.
+We will relate restricted permutations to placements of non-attacking
+rooks on a~hollow chessboard.
+
+\defn
+\itemize\ibull
+\:A~\df{board} is the grid $B=[n]\times [n]$. It consists of $n^2$ \df{squares.}
+\:A~\df{trace} of a~permutation $\pi\in{\cal P}$ is the set of squares $T(\pi)=\{ (i,\pi(i)) ; i\in[n] \}$.
+\endlist
+
+\obs\id{rooksobs}%
+The traces of permutations (and thus the permutations themselves) correspond
+exactly to placements of $n$ rooks at the board in a~way such that the rooks do
+not attack each other (i.e., there is at most one rook in every row and
+likewise in every column; as there are $n$~rooks, there must be exactly one of them in
+every row and column). When speaking about \df{rook placements,} we will always
+mean non-attacking placements.
+
+Restricted permutations then correspond to placements of rooks on a~board with
+some of the squares removed. The \df{holes} (missing squares) correspond to the
+non-edges of~$G$, so $\pi\in{\cal P}$ satisfies the restrictions iff
+$T(\pi)$ avoids the holes.
+
+\defn
+Let~$H\subseteq B$ be any set of holes in the board. Then:
+\itemize\ibull
+\:$N_j$ denotes the number of placements of $n$~rooks on the board such that exactly~$j$ of the rooks
+stand on holes. That is, $N_j := \#\{ \pi\in{\cal P} \mid \#(H\cap T(\pi)) = j \}$.
+\:$r_k$ is the number of ways how to place $k$~rooks on the holes. In other words,
+this is the number of $k$-element subsets of~$H$ such that no two elements share
+a~common row or column.
+\:$N$ is the generating function for the~$N_j$'s:
+$$
+N(x) = \sum_{j\ge 0} N_j x^j.
+$$
+As $N_j=0$ for $j>n$, this function is in fact a~finite polynomial.
+\endlist
+
+\thmn{The number of restricted permutations, Stanley \cite{stanley:econe}}
+The function~$N$ can be expressed in terms of the numbers~$r_k$ as:
+$$
+N(x) = \sum_{k=0}^n r_k \cdot (n-k)! \cdot (x-1)^k.
+$$
+
+\proof
+If two polynomials of degree~$n$ coincide at more than~$n$ points, they
+are identical, therefore it is sufficient to prove that the equality holds
+for all $x\in{\bb N}^+$.
+The $N(x)$ counts the ways of placing~$n$ rooks on the board and labeling
+each of them which stands on a~hole with an~element of~$[x]$. The right-hand
+side counts the same: We can obtain any such configuration by placing $k$~rooks
+on~$H$ first, labeling them with elements of~$\{2,\ldots,x\}$, placing
+additional $n-k$ rooks on the remaining rows and columns (there are $(n-k)!$ ways
+how to do this) and labeling those of the new rooks standing on a~hole with~1.
+\qed
+
+\cor
+When we substitute~$x=0$ in the above equality, we get a~formula for the
+number of rook placements avoiding the holes altogether:
+$$N_0 = N(0) = \sum_{k=0}^n (-1)^k \cdot (n-k)! \cdot r_k.$$
+
+\example\id{hatcheck}%
+Let us apply this theory to the hatcheck lady problem. The set~$H$ of holes is the main diagonal
+of the board: $H=\{ (i,i) \mid i\in[n] \}$. When we want to place $k$~rooks on the holes,
+we can do that in $r_k={n\choose k}$ ways. By the previous corollary, the number of
+derangements is:
+$$
+N_0 = \sum_{k=0}^n (-1)^k \cdot (n-k)! \cdot {n\choose k}
+ = \sum_{k=0}^n (-1)^k \cdot {n!\over k!}
+ = n! \cdot \sum_{k=0}^n {(-1)^k\over k!}.
+$$
+As the sum converges to~$1/e$ when $n$~approaches infinity, we know that the number
+of derangements is asymptotically $n!/e$.
+
+\obs\id{matchobs}%
+Placements of~$n$ rooks (and therefore also restricted permutations) can be
+also equated with perfect matchings in the restriction graph~$G$. The edges
+of the matching correspond to the squares occupied by the rooks, the condition
+that no two rooks share a~row nor column translates to the edges not touching
+each other, and the use of exactly~$n$ rooks is equivalent to the matching
+being perfect.
+
+There is also a~well-known correspondence between the perfect matchings
+in a~bipartite graph and non-zero summands in the formula for the permanent
+of the bipartite adjacency matrix~$M$ of the graph. This holds because the
+non-zero summands are in one-to-one correspondence with the placements
+of~$n$ rooks on the corresponding board. The number $N_0$ is therefore
+equal to the permanent of the matrix~$M$.
+
+We will summarize our observations in the following lemma:
+
+\lemma\id{permchar}%
+The following sets have the same cardinality:
+
+\itemize\ibull
+\:permutations which obey a~given restriction graph~$G$,
+\:non-attacking placements of rooks on a~$n\times n$ board avoiding holes
+ which correspond to non-edges of~$G$,
+\:perfect matchings in the graph~$G$,
+\:non-zero summands in the permanent of the adjacency matrix of~$G$.
+\endlist
+
+\proof
+See observations \ref{rooksobs} and~\ref{matchobs}.
+\qed
+
+\para
+The diversity of the characterizations of restricted permutations brings
+both good and bad news. The good news is that we can use the
+plethora of known results on bipartite matchings. Most importantly, we can efficiently
+determine whether there exists at least one permutation satisfying a~given set of restrictions:
+
+\thm
+There is an~algorithm which decides in time $\O(n^{1/2}\cdot m)$ whether there exists
+a~permutation satisfying a~given restriction graph.
+
+\proof
+It is sufficient to verify that there exists a~perfect matching in the
+given graph. By a~standard technique, this can be reduced in linear time to finding a~maximum
+flow in a~suitable unit-capacity network. This flow can be then found using the Dinic's
+algorithm in time $\O(\sqrt{n}\cdot m)$.
+(See \cite{dinic:flow} for the flow algorithm, \cite{even:dinic} for the time bound
+and \cite{schrijver} for more references on flows and matchings.)
+\qed
+
+\para
+The bad news is that computing the permanent is known to be~$\#P$-complete even
+for zero-one matrices (as proven by Valiant in \cite{valiant:permanent}).
+As a~ranking function for a~set of~matchings can be used to count all such
+matchings, we obtain the following theorem:
+
+\thm
+If there is a~polynomial-time algorithm for lexicographic ranking of permutations with
+a~set of restrictions which is a~part of the input, then $P=\#P$.
+
+\proof
+We will show that a~polynomial-time ranking algorithm would imply a~po\-ly\-nom\-ial-time
+algorithm for computing the permanent of an~arbitrary zero-one matrix, which
+is a~$\#P$-complete problem.
+
+We know from Lemma \ref{permchar} that non-zero
+summands in the permanent of a~zero-one matrix~$M$ correspond to permutations restricted
+by a~graph~$G$ whose bipartite adjacency matrix is~$M$. The permanent is
+therefore equal to the number of such permutations, which is one more than the
+rank of the lexicographically maximum such permutation.
+It therefore remains to show that we can find the lexicographically maximum
+permutation permitted by~$G$ in polynomial time.
+
+We can determine $\pi[1]$ by trying all the possible values permitted by~$G$
+in decreasing order and stopping as soon as we find~$\pi[1]$ which can be
+extended to a~complete permutation. This can be verified using the previous
+theorem on~the graph of the remaining restrictions, i.e., on~$G$ with the vertices
+1~on one side and~$\pi[1]$ on the other side removed.
+Once we have~$\pi[1]$, proceed by finding $\pi[2]$ in the same way, using the reduced
+graph. This way we construct the whole maximum permutation~$\pi$
+in~$\O(n^2)$ calls to the verification algorithm.
+\qed
+
+\para
+However, the hardness of computing the permanent is the only obstacle.
+We will show that whenever we are given a~set of restrictions for which
+the counting problem is easy (and it is also easy for subgraphs obtained
+by deleting vertices), ranking is easy as well. The key will be once again
+a~recursive structure, similar to the one we have seen in the case of plain
+permutations in \ref{permrec}.
+
+\nota\id{restnota}%
+As we will work with permutations on different sets simultaneously, we have
+to extend our notation accordingly. For every finite set of elements $A\subset{\bb N}$,
+we will consider the set ${\cal P}_A$ of all permutations on~$A$ as customary
+viewed as ordered $\vert A\vert$-tuples. The restriction graph will be represented
+by its adjacency matrix~$M\in \{0,1\}^{\vert A\vert\times \vert A\vert}$ and
+a~permutation $\pi\in{\cal P}_A$ satisfies~$M$ (conforms to the restrictions)
+iff $M[i,j]=1$ whenever $j=R_A(\pi[i])+1$.\foot{The $+1$ is added because
+matrices are indexed from~1 while the lowest rank is~0.}
+The set of all such~$\pi$ will be denoted by~${\cal P}_{A,M}$
+and their number (which obviously does not depend on the choice of~$A$) by $N_0(M) = {\per M}$.
+
+We will also frequently need to delete a~row and a~column simultaneously
+from~$M$. This operation corresponds to deletion of one vertex from each
+part of the restriction graph. We will write $M^{i,j}$ for the matrix~$M$
+with its $i$-th row and $j$-th column removed.
+
+\obs
+Let us consider a~permutation $\pi\in{\cal P}_A$ and $n=\vert A\vert$.
+When we fix the value of the element $\pi[1]$, the remaining elements form
+a~permutation $\pi'=\pi[2\ldots n]$ on the set~$A'=A\setminus\{\pi[1]\}$.
+The permutation~$\pi$ satisfies the restriction matrix~$M$ if and only if
+$M[1,a]=1$ for $a=R_A(\pi[1])$ and $\pi'$ satisfies a~restriction matrix~$M'=M^{1,a}$.
+This translates to the following counterparts of algorithms \ref{rankalg}
+and \ref{unrankalg}:
+
+\alg\id{rrankalg}%
+$\<Rank>(\pi,i,n,A,M)$: Compute the lexicographic rank of a~permutation $\pi[i\ldots n]\in{\cal P}_{A,M}$.
+
+\algo
+\:If $i\ge n$, return 0.
+\:$a\=R_A(\pi[i])$.
+\:$b\=C_a=\sum_k N_0(M^{1,k})$ over all $k$ such that $1\le k\le a$ and $M[1,k]=1$.
+ \cmt{$C_a$ is the number of permutations in ${\cal P}_{A,M}$ whose first element lies
+ among the first $a$ elements of~$A$.}
+\:Return $b + \<Rank>(\pi,i+1,n,A\setminus\{\pi[i]\},M^{1,a+1})$.
+\endalgo
+
+\>To calculate the rank of~$\pi\in{\cal P}_{A,M}$, we call $\<Rank>(\pi,1,\vert A\vert,A,M)$.
+
+\alg\id{runrankalg}%
+$\<Unrank>(j,i,n,A,M)$: Return an~array~$\pi$ such that $\pi[i,\ldots,n]$ is the $j$-th
+permutation in~${\cal P}_{A,M}$.
+
+\algo
+\:If $i>n$, return $(0,\ldots,0)$.
+\:Find minimum $a$ such that $C_a > j$ (where $C_a$ is as above).
+\:$x\=R^{-1}_A(a-1)$.
+\:$\pi\=\<Unrank>(j-C_{a-1}, i+1, n, A\setminus\{x\}, M^{1,a})$.
+\:$\pi[i]\=x$.
+\:Return~$\pi$.
+\endalgo
+
+\>To find the $j$-th permutation in~${\cal P}_{A,M}$, we call $\<Unrank>(j,1,\vert A\vert,A,M)$.
+
+\para
+The time complexity of these algorithms will be dominated by the computation of
+the numbers $C_a$, which requires a~linear amount of calls to~$N_0$ on every
+level of the recursion, and by the manipulation with matrices. Because of this,
+we do not any special data structure for the set~$A$, an~ordinary sorted array
+will suffice. (Also, we cannot use the vector representation blindly, because
+we have no guarantee that the word size is large enough.)
+
+\thmn{Lexicographic ranking of restricted permutations}
+Suppose that we have a~family of matrices ${\cal M}=\{M_1,M_2,\ldots\}$ such that $M_n\in \{0,1\}^{n\times n}$
+and it is possible to calculate the permanent of~$M'$ in time $\O(t(n))$ for every matrix $M'$
+obtained by deletion of rows and columns from~$M_n$. Then there exist algorithms
+for ranking and unranking in ${\cal P}_{A,M_n}$ in time $\O(n^4 + n^2\cdot t(n))$
+if $M_n$ and an~$n$-element set~$A$ are given as a~part of the input.
+
+\proof
+We will combine the algorithms \ref{rrankalg} and \ref{runrankalg} with the supplied
+function for computing the permanent. All matrices constructed by the algorithm
+are submatrices of~$M_n$ of the required type, so all computations of the function~$N_0$
+can be performed in time $\O(t(n))$ each.
+
+The recursion is $n$~levels deep. Every level involves
+a~constant number of (un)ranking operations on~$A$ and computation of at most~$n$
+of the $C_a$'s. Each such $C_a$ can be derived from~$C_{a-1}$ by constructing
+a~submatrix of~$M$ (which takes $\O(n^2)$ time) and computing its $N_0$. We therefore
+spend time $\O(n^2)$ on operations with the set~$A$, $\O(n^4)$ on matrix manipulations
+and $\O(n^2\cdot t(n))$ by the computations of the~$N_0$'s.
+\qed
+
+\rem
+In cases where the efficient evaluation of the permanent is out of our reach,
+we can consider using the fully-polynomial randomized approximation scheme
+for the permanent described by Jerrum, Sinclair and Vigoda in \cite{jerrum:permanent}.
+We then get an~approximation scheme for the ranks.
+
+\rem
+There are also deterministic algorithms for computing the number of perfect matchings
+in various special graph families (which imply polynomial-time ranking algorithms for
+the corresponding families of permutations). If the graph is planar, we can
+use the Kasteleyn's algorithm \cite{kasteleyn:crystals} based on Pfaffian
+orientations which runs in time $\O(n^3)$.
+It has been recently extended to arbitrary surfaces by Yuster and Zwick
+\cite{yuster:matching} and sped up to $\O(n^{2.19})$. The counting problem
+for arbitrary minor-closed classes (cf.~section \ref{minorclosed}) is still
+open.
+
+%--------------------------------------------------------------------------------
+
+\section{Hatcheck lady and other derangements}
+
+The time bound for ranking of general restricted permutations shown in the previous
+section is obviously very coarse. Its main purpose was to demonstrate that
+many special cases of the ranking problem can be indeed computed in polynomial time.
+For most families of restriction matrices, we can do much better. One of the possible improvements
+is to replace the matrix~$M$ by the corresponding restriction graph and instead of
+copying the matrix at every level of recursion, we perform local operations on the graph
+and undo them later. Another useful trick is to calculate the $N_0$'s of the smaller
+matrices using information already computed for the larger matrices.
+
+These speedups are hard to state formally in general (they depend on the
+structure of the matrices), so we will concentrate on a~specific example
+instead. We will show that for the derangements one can achieve linear time complexity.
+
+\nota\id{hatrank}%
+As we already know, the hatcheck permutations correspond to restriction
+matrices that contain zeroes only on the main diagonal and graphs that are
+complete bipartite with the matching $\{(i,i) \mid i\in[n]\}$ deleted. For
+a~given order~$n$, we will call this matrix~$D_n$ and the graph~$G_n$ and
+we will show that the submatrices of~$D_n$ share several nice properties:
+
+\lemma\id{submatrixlemma}%
+Let $D$ be a~submatrix of~$D_n$ obtained by deletion of rows and columns.
+Then the value of the permanent of~$D$ depends only on the size of~$D$
+and on the number of zero entries in~$D$.
+
+\proof
+We know from Lemma~\ref{permchar} that the permanent counts matchings in the
+graph~$G$ obtained from~$G_n$ by removing the vertices corresponding to the
+deleted rows and columns of~$D_n$. Therefore we can prove the lemma for
+the number of matchings instead.
+
+As~$G_n$ is a~complete bipartite graph without edges of a~single perfect matching,
+the graph~$G$ must be also complete bipartite with some non-touching edges
+missing. Two such graphs $G$ and~$G'$ are therefore isomorphic if and only if they have the
+same number of vertices and also the same number of missing edges. As the
+number of matchings is an~isomorphism invariant, the lemma follows.
+\qed
+
+\rem
+There is a~clear combinatorial intuition behind this lemma: if we are
+to count permutations with restrictions placed on~$z$ elements and these
+restrictions are independent, it does not matter how exactly they look like.
+
+\defn
+Let $n_0(z,d)$ be the permanent shared by all submatrices as described
+by the above lemma, which have $d\times d$ entries and exactly~$z$ zeroes.
+
+\lemma
+The function~$n_0$ satisfies the following recurrence:
+$$\eqalign{
+n_0(0,d) &= d!, \cr
+n_0(d,d) &= d! \cdot \sum\nolimits_{k=0}^d {(-1)^k \over k!}, \cr
+\noalign{\medskip}
+n_0(z,d) &= z\cdot n_0(z-1,d-1) + (d-z)\cdot n_0(z,d-1) \quad\hbox{for $z<d$.} \cr
+}\eqno{(*)}$$
+
+\proof
+The base cases of the recurrence are straightforward: $n_0(0,d)$ counts the
+unrestricted permutations on~$[d]$, and $n_0(d,d)$ is equal to the number of derangements
+on~$[d]$, which we have already computed in Observation \ref{hatcheck}. Let us
+prove the third formula.
+
+We will count the permutations~$\pi$ restricted by a~matrix~$M$ of the given parameters
+$z$ and~$d$. As $z<d$, there is at least one position in the permutation for which
+no restriction applies and by Lemma~\ref{submatrixlemma} we can choose without
+loss of generality that it is the first position.
+
+If we select $\pi[1]$ from the~$z$ restricted elements, the rest of~$\pi$ is a~permutation
+on the remaining elements with one restriction less and there are $n_0(z-1,d-1)$ such
+permutations. On the other hand, if we use an~unrestricted element, all restrictions
+stay in effect, so there are~$n_0(z,d-1)$ ways how to do so.
+\qed
+
+\lemma
+The function~$n_0$ also satisfies the following recurrence:
+$$
+n_0(z-1,d) = n_0(z,d) + n_0(z-1,d-1) \quad\hbox{for $z>0$, $d>0$.} \eqno{(\maltese)}
+$$
+
+\proof
+We will again take advantage of having proven Lemma~\ref{submatrixlemma}, which
+allows us to choose arbitrary matrices with the given parameters. Let us pick a~matrix~$M_z$
+containing $z$~zeroes such that $M_z[1,1]=0$. Then define~$M_{z-1}$ which is equal to~$M_z$
+everywhere except $M_{z-1}[1,1]=1$.
+
+We will count the permutations $\pi\in {\cal P}_d$ satisfying~$M_{z-1}$ in two ways.
+First, there are $n_0(z-1,d)$ such permutations. On the other hand, we can divide
+the them to two types depending on whether $\pi[1]=1$. Those having $\pi[1]\ne 1$
+are exactly the $n_0(z,d)$ permutations satisfying~$M_z$. The others correspond to
+permutations $(\pi[2],\ldots,\pi[d])$ on $\{2,\ldots,d\}$ that satisfy~$M_z^{1,1}$,
+so there are $n_0(z-1,d-1)$ of them.
+\qed
+
+\cor\id{nzeroprecalc}%
+For a~given~$n$, a~table of the values $n_0(z,d)$ for all $0\le z\le d\le n$
+can be precomputed in time~$\O(n^2)$.
+
+\proof
+Use either recurrence and induction on~$z+d$.
+\qed
+
+\cor\id{smalldiff}%
+For every $0\le z<d$ we have $n_0(z,d) - n_0(z+1,d) \le n_0(z,d)/d$.
+
+\proof
+According to the recurrence $(\maltese)$, the difference $n_0(z,d) - n_0(z+1,d)$ is
+equal to $n_0(z,d-1)$. We can bound this by plugging the trivial inequality $n_0(z,d-1) \le n_0(z-1,d-1)$
+to~$(*)$, from which we obtain $n_0(z,d) \ge d\cdot n_0(z,d-1)$.
+\qed
+
+\para\id{rrankmod}%
+Let us show how to modify the ranking algorithm (\ref{rrankalg}) using the insight
+we have gained into the structure of derangements.
+
+The algorithm uses the matrix~$M$ only for computing~$N_0$ of its submatrices
+and we have shown that this value depends only on the order of the matrix and
+the number of zeroes in it. We will therefore replace maintenance of the matrix
+by remember the number~$z$ of its zeroes and the set~$Z$ that contains the elements
+$x\in A$ whose locations are restricted (there is a~zero anywhere in the $(R_A(x)+1)$-th
+column of~$M$). In other words, every $x\in Z$ can appear at all positions in the
+permutation except one (and these forbidden positions are different for different~$x$'s),
+while the remaining elements of~$A$ can appear anywhere.
+
+As we already observed (\ref{hatcheck}) that the number of derangements on~$[n]$ is $\Theta(n!)$,
+we can again use word-sized vectors to represent the sets~$A$ and~$Z$ with insertion,
+deletion, ranking and unranking on them in constant time.
+
+When the algorithm selects a~submatrix $M'=M^{1,k}$ for an~element $x$ of~rank~$k-1$, this
+matrix it is described by either by the choice of $z'=z-1$ and~$Z'=Z\setminus\{x\}$ (if $x\in Z$)
+or $z'=z$ and $Z'=Z$ (if $x\not\in Z$).
+All computations of~$N_0$ in the algorithm can therefore be replaced by looking
+up the appropriate $n_0(z',\vert A\vert-1)$ in the precomputed table. Moreover, we can
+calculate a~single~$C_a$ in constant time, because all summands are either $n_0(z,\vert A\vert-1)$
+or $n_0(z-1,\vert A\vert-1)$ depending on the set~$Z$. We get:
+$$C_a = r\cdot n_0(z-1,\vert A\vert-1) + (a-r) \cdot n_0(z,\vert A\vert-1),$$
+where $r=R_Z(R^{-1}_A(a))$, that is the number of restricted elements among the $a$~smallest ones in~$A$.
+
+All operations at a~single level of the \<Rank> function now run in constant time,
+but \<Unrank> needs to search among the~$C_a$'s to find the first of them which
+exceeds the given rank. We could use binary search, but that would take $\Theta(\log n)$
+time. There is however a~clever trick: the value of~$C_a$ does not vary too much with
+the set~$Z$. Specifically, by Corollary~\ref{smalldiff} the difference between the values
+for $Z=\emptyset$ and $Z=A$ is at most $n_0(z-1,\vert A\vert -1)$. It is therefore
+sufficient to just divide the rank by $n_0(z-1,\vert A\vert-1)$ and we get either
+the correct value of~$a$ or one more. Both possibilities can be checked in constant time.
+
+We can therefore conclude this section by the following theorem:
+
+\thmn{Ranking of derangements}%
+For every~$n$, the derangements on the set~$[n]$ can be ranked and unranked according to the
+lexicographic order in time~$\O(n)$ after spending $\O(n^2)$ on initialization of auxiliary tables.
+
+\proof
+We modify the general algorithms for (un)ranking of restricted permutations (\ref{rrankalg} and \ref{runrankalg})
+as described above (\ref{rrankmod}). Each of the $n$~levels of recursion will then run in constant time. The values~$n_0$ will
+be looked up in a~table precalculated in quadratic time as shown in Corollary~\ref{nzeroprecalc}.
\qed
\endpart