More permutations.

[saga.git] / rank.tex

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

\chapter{Ranking Combinatorial Structures}

\section{Ranking and unranking}

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

\defn\id{rankdef}%
Let~$C$ be a~set of objects and~$\prec$ a~linear order on~$C$. The \df{rank}
$R_{C,\prec}(x)$ of an~element $x\in C$ is the number of elements $y\in C$ such that $y\prec x$.
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 the string~$x$.

\para
In this chapter, we will investigate how to compute the ranking and unranking
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.

\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}

One of the most common ranking problems is ranking of permutations on the set~$[n]=\{1,2,\ldots,n\}$.
This is frequently used to create arrays indexed by permutations: for example in Ruskey's algorithm
for finding Hamilton cycles in Cayley graphs (see~\cite{ruskey:ham} and \cite{ruskey:hce})
or when exploring state spaces of combinatorial puzzles like the Loyd's Fifteen \cite{ss:fifteen}.
Many other applications are surveyed by Critani et al.~in~\cite{critani:rau} and in
most cases, the time complexity of the whole algorithm is limited by the efficiency
of the (un)ranking functions.

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. 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
worst case \cite{reingold:catp} and even on average~\cite{liehe:raulow}.
This can be easily improved to $O(n\log n)$ by using either a binary search
tree to calculate inversions, or by a divide-and-conquer technique, or by clever
use of modular arithmetic (all three algorithms are described in
\cite{knuth:sas}). Myrvold and Ruskey \cite{myrvold:rank} mention further
improvements to $O(n\log n/\log \log n)$ by using the RAM data structures of Dietz
\cite{dietz:oal}.

Linear time complexity was reached by Myrvold and Ruskey \cite{myrvold:rank}
for a~non-lexicographic order, which is defined locally by the history of the
data structure --- in fact, they introduce a linear-time unranking algorithm
first and then they derive an inverse algorithm without describing the order
explicitly. However, they leave the problem of lexicographic ranking open.

We will describe a~general procedure which, when combined with suitable
RAM data structures, yields a~linear-time algorithm for lexicographic
(un)ranking.

\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.

\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])$.

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
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. 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 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$.
\id{rankalg}
\algo
\:If $i\ge n$, return~0.
\:$a\=R_A(\pi[i])$.
\:$b\=\<Rank>(\pi,i+1,n,A \setminus \{\pi[i]\})$.
\:Return $a\cdot(n-i)! + b$.
\endalgo

\>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$.
\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$.
\: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])$.

\para
The most time-consuming parts of the above algorithms are of course operations
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 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 calculations of factorials (which can be precomputed in~$\O(n)$ time),
or operations on the data structure.
\qed

\example
If we store~$A$ in an~ordinary array, we have insertion and deletion in constant time,
but ranking and unranking in~$\O(n)$, so $t(n)=\O(n)$ and the algorithm is quadratic.
Binary search trees give $t(n)=\O(\log n)$. The data structure of Dietz \cite{dietz:oal}
improves it to $t(n)=O(\log n/\log \log n)$. In fact, all these variants are equivalent
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]$.

\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)$.

\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{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$ 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)$.
\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 unraking.

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 {\secitfont k\/}-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 which 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{Hatcheck lady and other derangements}

Another interesting class of combinatorial objects which 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.

\nota\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$.

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
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
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
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$.

\defn
Let~$H\subseteq B$ be any set of squares called \df{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 \}$.
\:$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$, the 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
It is sufficient to prove that the equality holds for all integer~$x$.
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.
\qed

\cor
When we substitute~$x=0$ in the above equality, we get a~formula for the
number of rook placements avoiding~$H$:
$$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,
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
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:

\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$.

\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 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.
\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 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
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)$.

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.

\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]\}$.
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})$.
\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 $\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$.
\: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 $N_0(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~$N_0$. 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
This time bound is of course 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 improve the time complexity significantly,
for example by storing the matrix as a~graph and replacing the expensive copying of matrices
by local operations on the graph.

Instead of showing many little improvements for various restrictions, we will
concentrate on the case of derangements and show that it is possible to achieve
linear time complexity.

\examplen{Ranking of hatcheck permutations}\id{hatrank}%
As we already know, the hatcheck permutations (a.k.a.~derangements) correspond
to restriction matrices which contain zeroes only on the main diagonal. We will
call these matrices~$D_n$ and show that their submatrices have a~somewhat
surprising property:

\lemma
If $D$ is a~submatrix of~$D_n$ obtained by deletion of rows and columns.
Then the value $N_0(D)$ depends only on $n$ and the number of zero
entries in~$D$.

\proof
Let us note that if we exchange two rows or two columns of~$D$, the number $N_0(D)$ does not change.
If we swap the $i$-th and $j$-th row to get a~new matrix~$D'$, there is a~simple bijection
between the permutations permitted by~$D'$ and the permutations permitted by~$D$ --- it suffices
to swap the $i$-th and $j$-th element of the tuple. Similarly, swapping the $i$-th and $j$-th
column corresponds to exchanging the $i$-th and $j$-th smallest value in the tuple.

As the matrix $D_n$ contains exactly one zero in every row and column, the matrix
$D$ must contain at most one zero in every row and column. If it contains exactly $k$ zeroes,
we can therefore re-arrange it by row and column exchanges to the form in which the
zeroes are placed at the first~$k$ positions at the main diagonal. We therefore know
that $N_0(D)$ is the same as the~$N_0$ of this normalized matrix, which depends only on~$k$.
\qed



\endpart