\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
(un)ranking.
\nota\id{brackets}%
-We will view permutations on a~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 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
+\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])$. 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
+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]$,
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.
\>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
-\>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
\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.
+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
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$.
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 unraking.
+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
%--------------------------------------------------------------------------------
-\section{Ranking of {\secitfont k\/}-permutations}
+\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
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
+\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~$R$
-if for every~$i$, $(i,\pi(i))$ is an~edge of~$G$.
+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}.
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] \}$.
\endlist
-\obs
+\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 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.
-Restricted permutations then correspond to placements of rooks on a~restricted board,
-which we obtain by removing the squares corresponding to the non-edges of the restriction
-graph~$G$.
+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 squares called \df{holes} in the board. Then:
+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} \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(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 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
-Let us apply this theory to the hatcheck lady problem. The set~$H$ of holes is the diagonal
-of the board: $H=\{ (i,i) : i\in[n] \}$. When we want to place~$k$ rooks on the holes,
+\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:
$$
As the sum converges to~$1/e$ when $n$~approaches infinity, we know that the number
of derangements is asymptotically $n!/e$.
-\obs
-Restricted permutations (and thus rook placements) can be also equated with
-matchings in the restriction graph~$G$. Let us recall that the bipartite
-adjacency matrix of this graph corresponds to the board and zeroes in this
-matrix are at the places of the holes. A~perfect matching in~$G$ then
-corresponds to a~placement of $n$~rooks on the board.
-
-This brings both good and bad news. The good news is that we can use the
-plethora of known results on bipartite matchings. We can for example determine
-whether a~permutation satistying a~given set of restrictions exists
-by reducing 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)$ (see \cite{dinic:flow} for the algorithm,
-\cite{even:dinic} for the time bound and \cite{schrijver} for more references
-on flows and matchings), where $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)$.
-
-The bad news is that computing the number of such matchings is equivalent
-to computing a~permanent of the adjacency matrix of the graph~$G$ and permanents
-are 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:
+\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
-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~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. 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
-However, the hardness of computing the permanent is the worst obstacle.
+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.
+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
projects / saga.git / blobdiff