\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)$.
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{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{%
\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}
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}
\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 several nice properties:
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.
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\}$ which satisfy~$M_z^{1,1}$,
+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
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$ which contains the elements
+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),
projects / saga.git / blobdiff