\fi
\chapter{Ranking Combinatorial Structures}
+\id{rankchap}
\section{Ranking and unranking}
\nota\id{brackets}%
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 to index 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\id{permrec}%
Let us first observe that permutations have a simple recursive structure.
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])$. 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,\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
of permutations on a $(n-1)$-element set, which suggests a straightforward
\>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)$: Return an~array~$\pi$ such that $\pi[i,\ldots,n]$ is 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 $(0,\ldots,0)$.
-\:$a\=R^{-1}_A(\lfloor j/(n-i)! \rfloor)$.
-\:$\pi\=\<Unrank>(j\bmod (n-i)!,i+1,n,A\setminus \{a\})$.
-\:$\pi[i]\=a$.
+\:$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
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 which are smaller than~$x$, therefore $R_A(x)=x-R_H(x)$.
+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$.
%--------------------------------------------------------------------------------
-\section{Hatcheck lady and other derangements}
+\section{Restricted permutations}
-Another interesting class of combinatorial objects which can be counted and
+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{%
a~general (un)ranking method for any class of restricted permutations and
derive a~linear-time algorithm for the derangements from it.
-\nota\id{permnota}
+\defn\id{permnota}%
We will fix a~non-negative integer~$n$ and use ${\cal P}$ for the set of
all~permutations on~$[n]$.
-
-\defn
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 for every~$i$, $(i,\pi(i))$ is an~edge of~$G$.
+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}.
rooks on a~hollow chessboard.
\defn
-Let~$n$ be a~non-negative integer. Then:
\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] \}$.
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 in
+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.
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}: \#(H\cup T(\pi)) = j \}$.
+stand on holes. That is, $N_j := \#\{ \pi\in{\cal P}: \#(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(x) = \sum_{j\ge 0} N_j x^j.
$$
-As $N_j=0$ for $j>n$, the function is in fact a~finite polynomial.
+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}}
$$
\proof
-It is sufficient to prove that the equality holds for all integer~$x$.
+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 the new rooks standing on a~hole with~1.
+how to do this) and labeling those of the 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~$H$:
+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}%
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 or column translates to the edges not touching
+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.
\itemize\ibull
\:permutations which obey a~given restriction graph~$G$,
-\:non-attacking placements of rooks on a~$n\times n$ board avoiding holes,
+\: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$.
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 a~permutation satistying a~given set of restrictions exists:
-It is sufficient to reduce the corresponding matching problem to finding a~maximum flow in a~suitable
-unit-capacity network. The flow can be then found using the Dinic's algorithm
-in time $\O(\sqrt{n}\cdot m)$. Here $m$~is the number of edges in the network, which
-is linear in the size of the graph~$G$, therefore at worst $\Theta(n^2)$.
-(See \cite{dinic:flow} for the algorithm, \cite{even:dinic} for the time bound
+determine whether there exists at least one permutation satistying 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
\thm
If there is a~polynomial-time algorithm for lexicographic ranking of permutations with
-an~arbitrary set of restrictions (which is a~part of the input), then $P=\#P$.
+a~set of restrictions which is a~part of the input, then $P=\#P$.
\proof
-We will show that such a~ranking algorithm would enable us to compute the permanent
-of an~arbitrary zero-one matrix, which is a~$\#P$-complete problem. Let~$G$ be the
-bipartite graph with the bipartite adjacency matrix equal to the given matrix.
-The permanent of the matrix is then equal to the number of perfect matchings
-in~$G$, which is one more than the rank of the lexicographically maximal perfect
-matching in~$G$. As ranking of perfect matchings in~$G$ corresponds to ranking
-of permutations restricted by~$G$, it remains to show that we can find the
-lexicographically maximal permitted permutation in polynomial time.
+We will show that a~polynomial-time ranking algorithm would imply a~polynomial-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. We can do this for example by using the
-Dinic's algorithm as described above on~the graph of remaining restrictions
-(i.e., $G$ with the vertices 1 and~$\pi[1]$ and removed together with the corresponding
-edges). Once we have~$\pi[1]$, we can fix it and proceed by finding $\pi[2]$
-in the same way, using the reduced graph. This way we construct the whole
-maximal permutation~$\pi$ in~$\O(n^2)$ calls to the Dinic's algorithm.
+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
\nota\id{restnota}%
As we will work with permutations on different sets simultaneously, we have
-to extend our notation slightly. For every finite set of elements $A\subset{\bb N}$,
-we will consider the set ${\cal P}_A$ of all permutations on~$A$, as usually
+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~$A$) by $N_0(M) = {\per 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 $i$-th row and $j$-th column removed.
+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,\pi[n])$ on the set~$A'=A\setminus\{\pi[1]\}$.
+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}
\:$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})$.
+\: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)$.
\algo
\:If $i>n$, return $(0,\ldots,0)$.
-\:Find minimum $\ell$ such that $C_\ell > j$ (where $C_\ell$ is as above)
-\:$a\=R^{-1}_A(\ell-1)$.
-\:$\pi\=\<Unrank>(j-C_{\ell-1}, i+1, n, A\setminus\{a\}, M^{1,\ell})$.
-\:$\pi[i]\=a$.
+\: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
\qed
\rem
-This time bound is obviously very coarse, its main purpose was to demonstrate that
+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 such improvement
+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, perform local operations on the graph
+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 large matrices.
+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
-and we will show that for derangements one can achieve linear time complexity.
+instead. We will show that for the derangements one can achieve linear time complexity.
-\examplen{Ranking of hatcheck permutations a.k.a.~derangements}\id{hatrank}%
+\nota\id{hatrank}%
As we already know, the hatcheck permutations correspond to restriction
-matrices which contain zeroes only on the main diagonal and graphs which are
+matrices that contain zeroes only on the main diagonal and graphs that are
complete bipartite with the matching $\{(i,i) : 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 a~nice property:
+we will show that the submatrices of~$D_n$ share several nice properties:
\lemma\id{submatrixlemma}%
-If $D$ is a~submatrix of~$D_n$ obtained by deletion of rows and columns.
+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 the number of zero entries in it.
+and on the number of zero entries in~$D$.
\proof
We know from Lemma~\ref{permchar} that the permanent counts matchings in 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 matching,
+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 (but this matching is not necessarily perfect). 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 isomorphism invariant, the lemma follows.
+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.
-\para
-Instead of maintaining the matrix~$M$ in the algorithm, it is sufficient to keep
-the number~$z$ of zeroes in the matrix and the set~$Z$ which 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.
-
-The submatrix $M'=M^{1,k}$ for an~element $x$ of~rank~$k-1$ is described by either
-$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 a~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$. So 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$.
-
-It remains to show how to precompute the table of the $n_0$'s efficiently.
-
\lemma
The function~$n_0$ satisfies the following recurrence:
$$\eqalign{
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 simple: $n_0(0,d)$ counts the number of
-unrestricted permutations on~$[d]$ and $n_0(d,d)$ is equal to the number of derangements
+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.
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
projects / saga.git / blobdiff