From 0df3c88a5d5bf95c17912366d687defa69b12970 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Mon, 25 Feb 2008 18:37:36 +0100 Subject: [PATCH] More permutations. --- PLAN | 3 ++ macros.tex | 1 + notation.tex | 5 ++ rank.tex | 133 ++++++++++++++++++++++++++++++++++++++++++++++++--- 4 files changed, 135 insertions(+), 7 deletions(-) diff --git a/PLAN b/PLAN index b4699d6..228a8e0 100644 --- a/PLAN +++ b/PLAN @@ -67,11 +67,14 @@ Ranking: - move description of the ranking set to the chapter on models? - ranking of permutations on general sets, relationship with integer sorting - mention approximation of permanent +- mention \pi[x...y] Notation: +- use X+e, X-e for general sets? - \O(...) as a set? - G has to be connected, so m=O(n) - impedance mismatch in terminology: contraction of G along e vs. contraction of e. - use \delta(X) notation - unify use of n(G) vs. n +- use calligraphic letters from ams? diff --git a/macros.tex b/macros.tex index 2cf737f..dfaffe6 100644 --- a/macros.tex +++ b/macros.tex @@ -352,6 +352,7 @@ \def\defnn{\defn\labelx} \def\algn{\alg\label} \def\notan{\nota\labelx} +\def\examplen{\example\labelx} \def\proof{\noindent {\sl Proof.}\enspace} \def\proofsketch{\noindent {\sl Proof sketch.}\enspace} diff --git a/notation.tex b/notation.tex index a572fe3..1c8227e 100644 --- a/notation.tex +++ b/notation.tex @@ -69,6 +69,11 @@ \n{$H\minorof G$}{$H$ is a~minor of~$G$ \[minordef]} \n{$K_k$}{the complete graph on~$k$ vertices} \n{$C_k$}{the cycle on~$k$ vertices} +\n{${\cal P}_A$}{the set of all permutations on a~set~$A$ \[restnota]} +\n{${\cal P}_{A,M}$}{the set of all permutations on~$A$ satisfying the restrictions~$M$ \[restnota]} +\n{$N_0(M)$}{the number of permutations satisfying the restrictions~$M$ \[restnota]} +\n{$M^{i,j}$}{the matrix $M$ with $i$-th row and $j$-th column deleted \[restnota]} +\n{$D_n$}{the $n\times n$ matrix with $D[i,i]=0$ for all~$i$ and ones elsewhere else \[hatrank]} } %-------------------------------------------------------------------------------- diff --git a/rank.tex b/rank.tex index 2606aba..3a7e7e9 100644 --- a/rank.tex +++ b/rank.tex @@ -77,13 +77,13 @@ RAM data structures, yields a~linear-time algorithm for lexicographic (un)ranking. \nota\id{brackets}% -We will view permutations on a~set $A\subseteq {\bb N}$ as ordered $\vert A\vert$-tuples +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 +\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\}$. @@ -109,7 +109,7 @@ which uses the ranking function~$R_A$ for~$A$. This recursive formula immediatel translates to the following recursive algorithms for both ranking and unranking (described for example in \cite{knuth:sas}): -\alg $\(\pi,i,n,A)$: compute the rank of a~permutation $\pi[i\ldots n]$ on~$A$. +\alg $\(\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. @@ -302,13 +302,13 @@ 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 +\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~$R$ +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 @@ -432,10 +432,129 @@ maximal permutation~$\pi$ in~$\O(n^2)$ calls to the Dinic's algorithm. \qed \para -However, the hardness of computing the permanent is the worst obstacle. +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. +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}% +$\(\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 + \(\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 $\(\pi,1,\vert A\vert,A,M)$. + +\alg\id{runrankalg}% +$\(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\=\(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 $\(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 -- 2.39.5