\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
+The techniques for building efficient data structures on the RAM, which we have 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:
\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
+functions for different sets efficiently. Usually, we will observe
that the ranks (and hence the input and output of our algorithm) are large
numbers, so we can use the integers of a~similar magnitude to represent non-trivial
data structures.
This 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
+Many other applications are surveyed by Critani et al.~\cite{critani:rau} and in
most cases, the time complexity of the whole algorithm is limited by the efficiency
of the (un)ranking functions.
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
+use of modular arithmetic (all three algorithms are described in Knuth
\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}.
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])$,
-and sub-tuples: $\pi[i\ldots j] = (\pi[i],\ldots,\pi[j])$.
+and sub-tuples: $\pi[i\ldots j] = (\pi[i],\pi[i+1],\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.
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 n]$ and $\pi'[2\ldots n]$.
-Moreover, for fixed~$\pi[1]$ all permutations on the smaller set occur exactly
+Moreover, when we fix $\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]$.
\>We can call $\<Unrank>(j,1,n,[n])$ for the unranking problem on~$[n]$, i.e., to calculate $L^{-1}(j,[n])$.
-\para
+\paran{Representation of sets}%
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:
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}}
+\>Thus we get the following theorem:
+
+\thmn{Lexicographic ranking of permutations}
When we order the permutations on the set~$[n]$ lexicographically, both ranking
and unranking can be performed on the RAM in time~$\O(n)$.
\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
+on the data structure to allow the order of elements to depend on the history of the
structure (i.e., on the sequence of deletes performed so far). We can observe that
although the algorithm no longer gives the lexicographic ranks, the unranking function
is still an~inverse of the ranking function, because the sequence of deletes
-from~$A$ is the same when both ranking and unranking.
+from~$A$ is the same during 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 \iftoc $k$\else{\secitfont k\/}\fi-permutations}
\id{kpranksect}
-The technique from the previous section can be also generalized to lexicographic ranking of
-\df{$k$-permutations,} that is of ordered $k$-tuples drawn from the set~$[n]$.
+The ideas from the previous section can be also generalized to lexicographic ranking of
+\df{$k$-permutations,} that is of ordered $k$-tuples of distinct elements 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
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.
+we can precalculate all these values 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.
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
+are needed to represent the rank, so the vector representation of~$H$ certainly fits in
a~constant number of words.
\lemma
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$
+The only operation, which 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
we have just proven the following theorem, which brings this section to
a~happy ending:
-\thmn{Lexicographic ranking of $k$-permutations \cite{mm:rank}}
+\thmn{Lexicographic ranking of $k$-permutations}
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)$.
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
+was so confused that she was giving out the hats completely at random. 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.
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$.
+\paran{Boards and rooks}%
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
\defn
\itemize\ibull
\:A~\df{board} is the grid $B=[n]\times [n]$. It consists of $n^2$ \df{squares.}
-\:A~\df{trace} of a~permutation $\pi\in{\cal P}$ is the set of squares $T(\pi)=\{ (i,\pi(i)) ; i\in[n] \}$.
+\:A~\df{trace} of a~permutation $\pi\in{\cal P}$ is the set of squares \hbox{$T(\pi)=\{ (i,\pi(i)) ; i\in[n] \}$. \hskip-4em} %%HACK
\endlist
\obs\id{rooksobs}%
Let~$H\subseteq B$ be any set of holes in the board. Then:
\itemize\ibull
\:$N_j$ denotes the number of placements of $n$~rooks on the board such that exactly~$j$ of the rooks
-stand on holes. That is, $N_j := \#\{ \pi\in{\cal P} \mid \#(H\cap T(\pi)) = j \}$.
+stand on holes. That is:
+$$N_j := \bigl\vert\bigl\{ \pi\in{\cal P} \mathbin{\bigl\vert} \vert H\cap T(\pi) \vert = j \bigr\}\bigr\vert.$$
\:$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.
As the sum converges to~$1/e$ when $n$~approaches infinity, we know that the number
of derangements is asymptotically $n!/e$.
-\obs\id{matchobs}%
+\paran{Matchings and permanents}\id{matchper}%
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
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:
+We will summarize our observations by the following lemma:
\lemma\id{permchar}%
The following sets have the same cardinality:
\itemize\ibull
-\:permutations which obey a~given restriction graph~$G$,
+\:permutations that 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$,
+ that 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}.
+Follows from \ref{rooksobs} and~\ref{matchper}.
\qed
\para
\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.
+a~permutation satisfying a~given restriction graph. The $n$ and~$m$ are the number
+of vertices and edges of the 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.)
+(See Dinic \cite{dinic:flow} for the flow algorithm, Even and Tarjan \cite{even:dinic} for the time bound
+and Schrijver \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}).
+The bad news is that computing the permanent is known to be~$\#\rm P$-complete even
+for zero-one matrices (as proven by Valiant \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\id{pcomplete}%
If there is a~polynomial-time algorithm for lexicographic ranking of permutations with
-a~set of restrictions which is a~part of the input, then $P=\#P$.
+a~set of restrictions which is a~part of the input, then $\rm P=\#P$.
\proof
We will show that a~polynomial-time ranking algorithm would imply a~po\-ly\-nom\-ial-time
algorithm for computing the permanent of an~arbitrary zero-one matrix, which
-is a~$\#P$-complete problem.
+is a~$\#\rm 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
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.
+\looseness=1 %%HACK%%
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
in~$\O(n^2)$ calls to the verification algorithm.
\qed
-\para
+\paran{Recursive structure}%
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}.
+\looseness=1 %%HACK%%
\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
+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)
This translates to the following counterparts of algorithms \ref{rankalg}
and \ref{unrankalg}:
+\goodbreak %%HACK%%
\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$.
+\:$b\=C_a=\sum_k N_0(M^{1,k})$ over all $k$ such that $1\le k\le a$ and \hbox{$M[1,k]=1$.\kern-3pt} %%HACK
\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})$.
\algo
\:If $i>n$, return $(0,\ldots,0)$.
-\:Find minimum $a$ such that $C_a > j$ (where $C_a$ is as above).
+\:Find minimum $a$ such that $C_a > j$ (where $C_a$ is as in \<Rank> 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$.
\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
+level of recursion, and by the manipulation with matrices. Because of this,
+we do not need any sophisticated 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.)
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,
+\paran{Approximation}%
+In cases where 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
+for the permanent described by Jerrum, Sinclair and Vigoda \cite{jerrum:permanent}.
+They have described a~randomized algorithm that for every $\varepsilon>0$
+approximates the value of the permanent of an~$n\times n$ matrix with non-negative
+entries. The output is within relative error~$\varepsilon$ from the correct value with
+probability at least~$1/2$ and the algorithm runs in time polynomial in~$n$ and~$1/\varepsilon$.
+From this, we can get a~similar approximation scheme for the ranks.
+
+\paran{Special restriction graphs}%
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
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
+for arbitrary minor-closed classes (cf.~Section \ref{minorclosed}) is still
open.
%--------------------------------------------------------------------------------
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
+is replacing the matrix~$M$ by the corresponding restriction graph and instead of
+copying the matrix at every level of recursion, we can 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.
\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
+matrices that contain zeroes only on the main diagonal, and to 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:
\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
+on~$[d]$, which we have already computed in Example \ref{hatcheck}. Let us
prove the third formula.
We will count the permutations~$\pi$ restricted by a~matrix~$M$ of the given parameters
to~$(*)$, from which we obtain $n_0(z,d) \ge d\cdot n_0(z,d-1)$.
\qed
-\para\id{rrankmod}%
+\paran{The algorithm}\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
+by remembering 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),
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
+When the algorithm selects a~submatrix $M'=M^{1,k}$ for an~element~$x$ whose rank is~$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
+All computations of~$N_0$ in the algorithm can be therefore 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:
+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$.
projects / saga.git / blobdiff