From ded04da4d527e87c65f079a552e02b8ba8ff8e3b Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Wed, 27 Feb 2008 12:49:26 +0100 Subject: [PATCH] Nitpicking on the hatcheck lady. --- rank.tex | 87 ++++++++++++++++++++++++++++---------------------------- 1 file changed, 43 insertions(+), 44 deletions(-) diff --git a/rank.tex b/rank.tex index 3d5386e..0021e55 100644 --- a/rank.tex +++ b/rank.tex @@ -125,9 +125,9 @@ $L(\pi,[n])$. \id{unrankalg} \algo \:If $i>n$, return $(0,\ldots,0)$. -\:$a\=R^{-1}_A(\lfloor j/(n-i)! \rfloor)$. -\:$\pi\=\(j\bmod (n-i)!,i+1,n,A\setminus \{a\})$. -\:$\pi[i]\=a$. +\:$x\=R^{-1}_A(\lfloor j/(n-i)! \rfloor)$. +\:$\pi\=\(j\bmod (n-i)!,i+1,n,A\setminus \{x\})$. +\:$\pi[i]\=x$. \:Return~$\pi$. \endalgo @@ -302,14 +302,12 @@ the probability that none of the gentlemen receives his own hat?} We will presen 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} +\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 -if for every~$i$, $(i,\pi(i))$ is an~edge of~$G$. +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}. @@ -317,7 +315,6 @@ 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] \}$. @@ -327,7 +324,7 @@ Let~$n$ be a~non-negative integer. Then: 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. @@ -340,7 +337,7 @@ $T(\pi)$ avoids the holes. 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}: \#(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. @@ -348,7 +345,7 @@ 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}} @@ -358,18 +355,20 @@ 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$. +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 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\id{hatcheck}% @@ -389,7 +388,7 @@ of derangements is asymptotically $n!/e$. 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 or column translates to the edges not touching +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. @@ -407,7 +406,7 @@ 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, +\: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$. @@ -421,8 +420,8 @@ 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 a~permutation satistying a~given set of restrictions exists: -It is sufficient to reduce the corresponding matching problem to finding a~maximum flow in a~suitable +determine whether there exists at least one permutation satistying a~given set of restrictions: +It is sufficient to reduce the particular 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)$. Here $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)$. @@ -436,12 +435,12 @@ 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. +bipartite graph with its 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 @@ -468,20 +467,20 @@ 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 +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~$A$) by $N_0(M) = {\per 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 $i$-th row and $j$-th column removed. +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$. @@ -501,7 +500,7 @@ $\(\pi,i,n,A,M)$: Compute the lexicographic rank of a~permutation $\pi[i\l \:$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 + \(\pi,i+1,n,A\setminus\{\pi[i]\},M^{1,a})$. +\:Return $b + \(\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 $\(\pi,1,\vert A\vert,A,M)$. @@ -512,10 +511,10 @@ 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\=\(j-C_{\ell-1}, i+1, n, A\setminus\{a\}, M^{1,\ell})$. -\:$\pi[i]\=a$. +\:Find minimum $a$ such that $C_a > j$ (where $C_a$ is as above). +\:$x\=R^{-1}_A(a-1)$. +\:$\pi\=\(j-C_{a-1}, i+1, n, A\setminus\{x\}, M^{1,a})$. +\:$\pi[i]\=x$. \:Return~$\pi$. \endalgo @@ -553,15 +552,15 @@ and $\O(n^2\cdot t(n))$ by the computations of the~$N_0$'s. \rem This time bound 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 such improvement +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, perform local operations on the graph +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 large matrices. +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 -and we will show that for derangements one can achieve linear time complexity. +instead. We will show that for derangements one can achieve linear time complexity. \examplen{Ranking of hatcheck permutations a.k.a.~derangements}\id{hatrank}% As we already know, the hatcheck permutations correspond to restriction @@ -571,9 +570,9 @@ 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 a~nice property: \lemma\id{submatrixlemma}% -If $D$ is a~submatrix of~$D_n$ obtained by deletion of rows and columns. +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 the number of zero entries in it. +and on the number of zero entries in~$D$. \proof We know from Lemma~\ref{permchar} that the permanent counts matchings in the @@ -581,12 +580,12 @@ 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 matching, +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 (but this matching is not necessarily perfect). 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 isomorphism invariant, the lemma follows. +As the number of matchings is an~isomorphism invariant, the lemma follows. \qed \defn @@ -594,8 +593,8 @@ 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. \para -Instead of maintaining the matrix~$M$ in the algorithm, it is sufficient to keep -the number~$z$ of zeroes in the matrix and the set~$Z$ which contains the elements +Instead of maintaining the matrix~$M$ over the course of the algorithm, it is sufficient to remember +the number~$z$ of zeroes in this matrix and the set~$Z$ which 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), @@ -606,12 +605,12 @@ we can again use word-sized vectors to represent the sets~$A$ and~$Z$ with inser deletion, ranking and unranking on them in constant time. The submatrix $M'=M^{1,k}$ for an~element $x$ of~rank~$k-1$ is described by either -$z'=z-1$ and~$Z'=Z\setminus\{x\}$ (if $x\in Z$) or $z'=z$ and $Z'=Z'$ (if $x\not\in Z$). +$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 a~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$. So we get: -$$C_a = r\cdot n_0(z+1,\vert A\vert-1) + (a-r) \cdot n_0(z,\vert A\vert-1),$$ +or $n_0(z-1,\vert A\vert-1)$ depending on the set~$Z$. So 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$. It remains to show how to precompute the table of the $n_0$'s efficiently. @@ -626,8 +625,8 @@ n_0(z,d) &= z\cdot n_0(z-1,d-1) + (d-z)\cdot n_0(z,d-1) \quad\hbox{for $z