More of the prolog.

[saga.git] / rank.tex

diff --git a/rank.tex b/rank.tex
index bcf76572ea4b27c993f3063a69d32d30cfb11521..014d56d4af97000a8f3593f26d96aec6e5a1c0c0 100644 (file)
--- a/rank.tex
+++ b/rank.tex
@@ -5,7 +5,7 @@
 \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
@@ -148,7 +148,7 @@ Then lexicographic ranking and unranking of permutations can be performed in tim
 
 \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
@@ -195,7 +195,7 @@ 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.
+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
@@ -365,7 +365,7 @@ 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 those of the 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
@@ -422,7 +422,7 @@ See observations \ref{rooksobs} and~\ref{matchobs}.
 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 satistying a~given set of restrictions:
+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
@@ -741,6 +741,4 @@ as described above (\ref{rrankmod}). Each of the $n$~levels of recursion will th
 be looked up in a~table precalculated in quadratic time as shown in Corollary~\ref{nzeroprecalc}.
 \qed
 
-
-
 \endpart