5 \chapter{Ranking Combinatorial Structures}
7 \section{Ranking and unranking}
9 The techniques for building efficient data structures on the RAM described
10 in Chapter~\ref{ramchap} can be also used for a~variety of problems related
11 to ranking of combinatorial structures. Generally, the problems are stated
15 Let~$C$ be a~set of objects and~$\prec$ a~linear order on~$C$. The \df{rank}
16 $R_{C,\prec}(x)$ of an~element $x\in C$ is the number of elements $y\in C$ such that $y\prec x$.
17 We will call the function $R_{C,\prec}$ the \df{ranking function} for $C$ ordered by~$\prec$
18 and its inverse $R^{-1}_{C,\prec}$ the \df{unranking function} for $C$ and~$\prec$. When the set
19 and the order are clear from the context, we will use plain~$R(x)$ and $R^{-1}(x)$.
20 Also, when $\prec$ is defined on a~superset~$C'$ of~$C$, we naturally extend $R_C(x)$
21 to elements $x\in C'\setminus C$.
24 Let us consider the set $C_k=\{\0,\1\}^k$ of all binary strings of length~$k$ ordered
25 lexicographically. Then $R^{-1}(i)$ is the $i$-th smallest element of this set, that
26 is the number~$i$ written in binary and padded to~$k$ digits (i.e., $\(i)_k$ in the
27 notation of Section~\ref{bitsect}). Obviously, $R(x)$ is the integer whose binary
28 representation is the string~$x$.
31 In this chapter, we will investigate how to compute the ranking and unranking
32 functions for different sets efficiently. Usually, we will make use of the fact
33 that the ranks (and hence the input and output of our algorithm) are large
34 numbers, so we can use the integers of a~similar magnitude to represent non-trivial
38 Until the end of the chapter, we will always assume that our model of computation
39 is the Random Access Machine (more specifically, the Word-RAM).
41 %--------------------------------------------------------------------------------
43 \section{Ranking of permutations}
46 One of the most common ranking problems is ranking of permutations on the set~$[n]=\{1,2,\ldots,n\}$.
47 This is frequently used to create arrays indexed by permutations: for example in Ruskey's algorithm
48 for finding Hamilton cycles in Cayley graphs (see~\cite{ruskey:ham} and \cite{ruskey:hce})
49 or when exploring state spaces of combinatorial puzzles like the Loyd's Fifteen \cite{ss:fifteen}.
50 Many other applications are surveyed by Critani et al.~in~\cite{critani:rau} and in
51 most cases, the time complexity of the whole algorithm is limited by the efficiency
52 of the (un)ranking functions.
54 The permutations are usually ranked according to their lexicographic order.
55 In fact, an~arbitrary order is often sufficient if the ranks are used solely
56 for indexing of arrays. The lexicographic order however has an~additional advantage
57 of a~nice structure, which allows various operations on permutations to be
58 performed directly on their ranks.
60 Na\"\i{}ve algorithms for lexicographic ranking require time $\Theta(n^2)$ in the
61 worst case \cite{reingold:catp} and even on average~\cite{liehe:raulow}.
62 This can be easily improved to $O(n\log n)$ by using either a binary search
63 tree to calculate inversions, or by a divide-and-conquer technique, or by clever
64 use of modular arithmetic (all three algorithms are described in
65 \cite{knuth:sas}). Myrvold and Ruskey \cite{myrvold:rank} mention further
66 improvements to $O(n\log n/\log \log n)$ by using the RAM data structures of Dietz
69 Linear time complexity was reached by Myrvold and Ruskey \cite{myrvold:rank}
70 for a~non-lexicographic order, which is defined locally by the history of the
71 data structure --- in fact, they introduce a linear-time unranking algorithm
72 first and then they derive an inverse algorithm without describing the order
73 explicitly. However, they leave the problem of lexicographic ranking open.
75 We will describe a~general procedure which, when combined with suitable
76 RAM data structures, yields a~linear-time algorithm for lexicographic
80 We will view permutations on a~finite set $A\subseteq {\bb N}$ as ordered $\vert A\vert$-tuples
81 (in other words, arrays) containing every element of~$A$ exactly once. We will
82 use square brackets to index these tuples: $\pi=(\pi[1],\ldots,\pi[\vert A\vert])$,
83 and sub-tuples: $\pi[i\ldots j] = (\pi[i],\ldots,\pi[j])$.
84 The lexicographic ranking and unranking functions for the permutations on~$A$
85 will be denoted by~$L(\pi,A)$ and $L^{-1}(i,A)$ respectively.
88 Let us first observe that permutations have a simple recursive structure.
89 If we fix the first element $\pi[1]$ of a~permutation~$\pi$ on the set~$[n]$, the
90 elements $\pi[2], \ldots, \pi[n]$ form a~permutation on $[n]-\{\pi[1]\} = \{1,\ldots,\pi[1]-1,\pi[1]+1,\ldots,n\}$.
91 The lexicographic order of two permutations $\pi$ and~$\pi'$ on the original set is then determined
92 by $\pi[1]$ and $\pi'[1]$ and only if these elements are equal, it is decided
93 by the lexicographic comparison of permutations $\pi[2\ldots n]$ and $\pi'[2\ldots n]$.
94 Moreover, for fixed~$\pi[1]$ all permutations on the smaller set occur exactly
95 once, so the rank of $\pi$ is $(\pi[1]-1)\cdot (n-1)!$ plus the rank of
98 This gives us a~reduction from (un)ranking of permutations on $[n]$ to (un)ranking
99 of permutations on a $(n-1)$-element set, which suggests a straightforward
100 algorithm, but unfortunately this set is different from $[n-1]$ and it even
101 depends on the value of~$\pi[1]$. We could renumber the elements to get $[n-1]$,
102 but it would require linear time per iteration. To avoid this, we generalize the
103 problem to permutations on subsets of $[n]$. For a permutation $\pi$ on a~set
104 $A\subseteq [n]$ of size~$m$, similar reasoning gives a~simple formula:
106 L((\pi[1],\ldots,\pi[m]),A) = R_A(\pi[1]) \cdot (m-1)! +
107 L((\pi[2],\ldots,\pi[m]), A\setminus\{\pi[1]\}),
109 which uses the ranking function~$R_A$ for~$A$. This recursive formula immediately
110 translates to the following recursive algorithms for both ranking and unranking
111 (described for example in \cite{knuth:sas}):
113 \alg $\<Rank>(\pi,i,n,A)$: Compute the rank of a~permutation $\pi[i\ldots n]$ on~$A$.
116 \:If $i\ge n$, return~0.
118 \:$b\=\<Rank>(\pi,i+1,n,A \setminus \{\pi[i]\})$.
119 \:Return $a\cdot(n-i)! + b$.
122 \>We can call $\<Rank>(\pi,1,n,[n])$ for ranking on~$[n]$, i.e., to calculate
125 \alg $\<Unrank>(j,i,n,A)$: Return an~array~$\pi$ such that $\pi[i\ldots n]$ is the $j$-th permutation on~$A$.
128 \:If $i>n$, return $(0,\ldots,0)$.
129 \:$x\=R^{-1}_A(\lfloor j/(n-i)! \rfloor)$.
130 \:$\pi\=\<Unrank>(j\bmod (n-i)!,i+1,n,A\setminus \{x\})$.
135 \>We can call $\<Unrank>(j,1,n,[n])$ for the unranking problem on~$[n]$, i.e., to get $L^{-1}(j,[n])$.
138 The most time-consuming parts of the above algorithms are of course operations
139 on the set~$A$. If we store~$A$ in a~data structure of a~known time complexity, the complexity
140 of the whole algorithm is easy to calculate:
142 \lemma\id{ranklemma}%
143 Suppose that there is a~data structure maintaining a~subset of~$[n]$ under a~sequence
144 of deletions, which supports ranking and unranking of elements, and that
145 the time complexity of a~single operation is at most~$t(n)$.
146 Then lexicographic ranking and unranking of permutations can be performed in time $\O(n\cdot t(n))$.
149 Let us analyse the above algorithms. The depth of the recursion is~$n$ and in each
150 nested invokation of the recursive procedure we perform a~constant number of operations.
151 All of them are either trivial, or calculations of factorials (which can be precomputed in~$\O(n)$ time),
152 or operations on the data structure.
156 If we store~$A$ in an~ordinary array, we have insertion and deletion in constant time,
157 but ranking and unranking in~$\O(n)$, so $t(n)=\O(n)$ and the algorithm is quadratic.
158 Binary search trees give $t(n)=\O(\log n)$. The data structure of Dietz \cite{dietz:oal}
159 improves it to $t(n)=O(\log n/\log \log n)$. In fact, all these variants are equivalent
160 to the classical algorithms based on inversion vectors, because at the time of processing~$\pi[i]$,
161 the value of $R_A(\pi[i])$ is exactly the number of elements forming inversions with~$\pi[i]$.
164 To obtain linear time complexity, we will make use of the representation of
165 vectors by integers on the RAM as developed in Section~\ref{bitsect}, but first
166 of all, we will make sure that the ranks are large numbers, so the word size of the
167 machine has to be large as well:
170 $\log n! = \Theta(n\log n)$, therefore the word size~$W$ must be~$\Omega(n\log n)$.
173 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$.
176 \thmn{Lexicographic ranking of permutations \cite{mm:rank}}
177 When we order the permutations on the set~$[n]$ lexicographically, both ranking
178 and unranking can be performed on the RAM in time~$\O(n)$.
181 We will store the elements of the set~$A$ in a~sorted vector. Each element has
182 $\O(\log n)$ bits, so the whole vector takes $\O(n\log n)$ bits, which by the
183 above observation fits in a~constant number of machine words. We know from
184 Algorithm~\ref{vecops} that ranks can be calculated in constant time in such
185 vectors and that insertions and deletions can be translated to ranks and
186 masking. Unranking, that is indexing of the vector, is masking alone.
187 So we can apply the previous Lemma \ref{ranklemma} with $t(n)=\O(1)$.
191 We can also easily derive the non-lexicographic linear-time algorithm of Myrvold
192 and Ruskey~\cite{myrvold:rank} from our algorithm. We will relax the requirements
193 on the data structure to allow order of elements dependent on the history of the
194 structure (i.e., on the sequence of deletes performed so far). We can observe that
195 although the algorithm no longer gives the lexicographic ranks, the unranking function
196 is still an~inverse of the ranking function, because the sequence of deletes
197 from~$A$ is the same when both ranking and unraking.
199 The implementation of the relaxed structure is straightforward. We store the set~$A$
200 in an~array~$\alpha$ and use the order of the elements in~$\alpha$ determine the
201 order on~$A$. We will also maintain an~``inverse'' array $\alpha^{-1}$ such that
202 $\alpha[\alpha^{-1}[x]]=x$ for every~$x\in A$. Ranking and unranking can be performed
203 by a~simple lookup in these arrays: $R_A(x)=\alpha^{-1}[x]$, $R^{-1}(i)=\alpha[i]$.
204 When we want to delete an~element, we exchange it with the last element in the
205 array~$\alpha$ and update~$\alpha^{-1}$ accordingly.
208 %--------------------------------------------------------------------------------
210 \section{Ranking of {\secitfont k\/}-permutations}
213 The technique from the previous section can be also generalized to lexicographic ranking of
214 \df{$k$-permutations,} that is of ordered $k$-tuples drawn from the set~$[n]$.
215 There are $n^{\underline k} = n\cdot(n-1)\cdot\ldots\cdot(n-k+1)$
216 such $k$-permutations and they have a~recursive structure similar to the one of
217 the permutations. We will therefore use the same recursive scheme as before
218 (algorithms \ref{rankalg} and \ref{unrankalg}), but we will modify the first step of both algorithms
219 to stop after the first~$k$ iterations. We will also replace the number $(n-i)!$
220 of permutations on the remaining elements by the number of $(k-i)$-permutations on the same elements,
221 i.e., by $(n-i)^{\underline{k-i}}$. As $(n-i)^{\underline{k-i}} = (n-i) \cdot (n-i-1)^{\underline{k-i-1}}$,
222 we can precalculate all these numbers in linear time.
224 Unfortunately, the ranks of $k$-permutations can be much smaller, so we can no
225 longer rely on the same data structure fitting in a constant number of word-sized integers.
226 For example, if $k=1$, the ranks are $\O(\log n)$-bit numbers, but the data
227 structure still requires $\Theta(n\log n)$ bits.
229 We do a minor side step by remembering the complement of~$A$ instead, that is
230 the set of the at most~$k$ elements we have already seen. We will call this set~$H$
231 (because it describes the ``holes'' in~$A$). Let us prove that $\Omega(k\log n)$ bits
232 are needed to represent the rank, so the vector representation of~$H$ fits in
233 a~constant number of words.
236 The number of $k$-permutations on~$[n]$ is $2^{\Omega(k\log n)}$.
239 We already know that there $n^{\underline k}$ such $k$-permutations. If $k\le n/2$,
240 then every term in the product is $n/2$ or more, so $\log n^{\underline k} \ge
241 k\cdot (\log n - 1)$. If $k\ge n/2$, then $n^{\underline k} \ge n^{\underline{\smash{n/2}}}$
242 and $\log n^{\underline k} \ge (n/2)(\log n - 1) \ge (k/2)(\log n - 1)$.
246 It remains to show how to translate the operations on~$A$ to operations on~$H$,
247 again stored as a~sorted vector~${\bf h}$. Insertion to~$A$ correspond to
248 deletion from~$H$ and vice versa. The rank of any~$x\in[n]$ in~$A$ is $x$ minus
249 the number of holes which are smaller than~$x$, therefore $R_A(x)=x-R_H(x)$.
250 To calculate $R_H(x)$, we can again use the vector operation \<Rank> from Algorithm \ref{vecops},
251 this time on the vector~$\bf h$.
253 The only operation we cannot translate directly is unranking in~$A$. We will
254 therefore define an~auxiliary vector~$\bf r$ of the same size as~$\bf h$
255 containing the ranks of the holes: $r_i=R_A(h_i)=h_i-R_H(h_i)=h_i-i$.
256 To find the $j$-th smallest element of~$A$, we locate the interval between
257 holes to which this element belongs: the interval is bordered from below by
258 a~hole~$h_i$ such that $i$ is the largest index satisfying~$r_i \le j$.
259 In other words, $i=\<Rank>(r,j+1)-1$. Finding the right element in the interval
260 is then easy: $R^{-1}_A(j) = h_i + 1 + j - r_i$.
263 If $A=\{2,5,6\}$ and $n=8$, then ${\bf h}=(1,3,4,7,8)$ and ${\bf r}
264 = (0,1,1,3,3)$. When we want to calculate $R^{-1}_A(2)$, we find $i=2$ and
265 the wanted element is $h_2+1+2-r_2 = 4+1+2-1 = 6$.
268 The vector~$\bf r$ can be updated in constant time whenever an~element is
269 inserted to~$\bf h$. It is sufficient to shift the fields apart (we know
270 that the position of the new element in~$\bf r$ is the same as in~$\bf h$),
271 insert the new value using masking operations and decrease all higher fields
272 by one in parallel by using a~single subtraction. Updates after deletions
273 from~$\bf h$ are analogous.
275 We have replaced all operations on~$A$ by the corresponding operations on the
276 modified data structure, each of which works again in constant time. Therefore
277 we have just proven the following theorem, which brings this section to
280 \thmn{Lexicographic ranking of $k$-permutations \cite{mm:rank}}
281 When we order the $k$-per\-mu\-ta\-tions on the set~$[n]$ lexicographically, both
282 ranking and unranking can be performed on the RAM in time~$\O(k)$.
285 We modify algorithms \ref{rankalg} and \ref{unrankalg} for $k$-permutations as
286 shown at the beginning of this section. We use the vectors $\bf h$ and~$\bf r$
287 described above as an~implicit representation of the set~$A$. The modified
288 algorithm uses recursion $k$~levels deep and as each operation on~$A$ can be
289 performed in~$\O(1)$ time using $\bf h$ and~$\bf r$, every level takes only
290 constant time. The time bound follows. \qed
292 %--------------------------------------------------------------------------------
294 \section{Restricted permutations}
296 Another interesting class of combinatorial objects which can be counted and
297 ranked are restricted permutations. An~archetypal member of this class are
298 permutations without a~fixed point, i.e., permutations~$\pi$ such that $\pi(i)\ne i$
299 for all~$i$. These are also called \df{derangements} or \df{hatcheck permutations.}\foot{%
300 As the story in~\cite{matnes:idm} goes, once upon a~time there was a~hatcheck lady who
301 was so confused that she was giving out the hats completely randomly. What is
302 the probability that none of the gentlemen receives his own hat?} We will present
303 a~general (un)ranking method for any class of restricted permutations and
304 derive a~linear-time algorithm for the derangements from it.
307 We will fix a~non-negative integer~$n$ and use ${\cal P}$ for the set of
308 all~permutations on~$[n]$.
309 A~\df{restriction graph} is a~bipartite graph~$G$ whose parts are two copies
310 of the set~$[n]$. A~permutation $\pi\in{\cal P}$ satisfies the restrictions
311 if $(i,\pi(i))$ is an~edge of~$G$ for every~$i$.
313 We will follow the path unthreaded by Kaplansky and Riordan
314 \cite{kaplansky:rooks} and charted by Stanley in \cite{stanley:econe}.
315 We will relate restricted permutations to placements of non-attacking
316 rooks on a~hollow chessboard.
320 \:A~\df{board} is the grid $B=[n]\times [n]$. It consists of $n^2$ \df{squares.}
321 \:A~\df{trace} of a~permutation $\pi\in{\cal P}$ is the set of squares $T(\pi)=\{ (i,\pi(i)) ; i\in[n] \}$.
325 The traces of permutations (and thus the permutations themselves) correspond
326 exactly to placements of $n$ rooks at the board in a~way such that the rooks do
327 not attack each other (i.e., there is at most one rook in every row and
328 likewise in every column; as there are $n$~rooks, there must be exactly one of them in
329 every row and column). When speaking about \df{rook placements,} we will always
330 mean non-attacking placements.
332 Restricted permutations then correspond to placements of rooks on a~board with
333 some of the squares removed. The \df{holes} (missing squares) correspond to the
334 non-edges of~$G$, so $\pi\in{\cal P}$ satisfies the restrictions iff
335 $T(\pi)$ avoids the holes.
338 Let~$H\subseteq B$ be any set of holes in the board. Then:
340 \:$N_j$ denotes the number of placements of $n$~rooks on the board such that exactly~$j$ of the rooks
341 stand on holes. That is, $N_j := \#\{ \pi\in{\cal P}: \#(H\cap T(\pi)) = j \}$.
342 \:$r_k$ is the number of ways how to place $k$~rooks on the holes. In other words,
343 this is the number of $k$-element subsets of~$H$ such that no two elements share
344 a~common row or column.
345 \:$N$ is the generating function for the~$N_j$'s:
347 N(x) = \sum_{j\ge 0} N_j x^j.
349 As $N_j=0$ for $j>n$, this function is in fact a~finite polynomial.
352 \thmn{The number of restricted permutations, Stanley \cite{stanley:econe}}
353 The function~$N$ can be expressed in terms of the numbers~$r_k$ as:
355 N(x) = \sum_{k=0}^n r_k \cdot (n-k)! \cdot (x-1)^k.
359 If two polynomials of degree~$n$ coincide at more than~$n$ points, they
360 are identical, therefore it is sufficient to prove that the equality holds
361 for all $x\in{\bb N}^+$.
362 The $N(x)$ counts the ways of placing~$n$ rooks on the board and labeling
363 each of them which stands on a~hole with an~element of~$[x]$. The right-hand
364 side counts the same: We can obtain any such configuration by placing $k$~rooks
365 on~$H$ first, labeling them with elements of~$\{2,\ldots,x\}$, placing
366 additional $n-k$ rooks on the remaining rows and columns (there are $(n-k)!$ ways
367 how to do this) and labeling those of the the new rooks standing on a~hole with~1.
371 When we substitute~$x=0$ in the above equality, we get a~formula for the
372 number of rook placements avoiding the holes altogether:
373 $$N_0 = N(0) = \sum_{k=0}^n (-1)^k \cdot (n-k)! \cdot r_k.$$
375 \example\id{hatcheck}%
376 Let us apply this theory to the hatcheck lady problem. The set~$H$ of holes is the main diagonal
377 of the board: $H=\{ (i,i) : i\in[n] \}$. When we want to place $k$~rooks on the holes,
378 we can do that in $r_k={n\choose k}$ ways. By the previous corollary, the number of
381 N_0 = \sum_{k=0}^n (-1)^k \cdot (n-k)! \cdot {n\choose k}
382 = \sum_{k=0}^n (-1)^k \cdot {n!\over k!}
383 = n! \cdot \sum_{k=0}^n {(-1)^k\over k!}.
385 As the sum converges to~$1/e$ when $n$~approaches infinity, we know that the number
386 of derangements is asymptotically $n!/e$.
389 Placements of~$n$ rooks (and therefore also restricted permutations) can be
390 also equated with perfect matchings in the restriction graph~$G$. The edges
391 of the matching correspond to the squares occupied by the rooks, the condition
392 that no two rooks share a~row nor column translates to the edges not touching
393 each other, and the use of exactly~$n$ rooks is equivalent to the matching
396 There is also a~well-known correspondence between the perfect matchings
397 in a~bipartite graph and non-zero summands in the formula for the permanent
398 of the bipartite adjacency matrix~$M$ of the graph. This holds because the
399 non-zero summands are in one-to-one correspondence with the placements
400 of~$n$ rooks on the corresponding board. The number $N_0$ is therefore
401 equal to the permanent of the matrix~$M$.
403 We will summarize our observations in the following lemma:
406 The following sets have the same cardinality:
409 \:permutations which obey a~given restriction graph~$G$,
410 \:non-attacking placements of rooks on a~$n\times n$ board avoiding holes
411 which correspond to non-edges of~$G$,
412 \:perfect matchings in the graph~$G$,
413 \:non-zero summands in the permanent of the adjacency matrix of~$G$.
417 See observations \ref{rooksobs} and~\ref{matchobs}.
421 The diversity of the characterizations of restricted permutations brings
422 both good and bad news. The good news is that we can use the
423 plethora of known results on bipartite matchings. Most importantly, we can efficiently
424 determine whether there exists at least one permutation satistying a~given set of restrictions:
427 There is an~algorithm which decides in time $\O(n^{1/2}\cdot m)$ whether there exists
428 a~permutation satisfying a~given restriction graph.
431 It is sufficient to verify that there exists a~perfect matching in the
432 given graph. By a~standard technique, this can be reduced in linear time to finding a~maximum
433 flow in a~suitable unit-capacity network. This flow can be then found using the Dinic's
434 algorithm in time $\O(\sqrt{n}\cdot m)$.
435 (See \cite{dinic:flow} for the flow algorithm, \cite{even:dinic} for the time bound
436 and \cite{schrijver} for more references on flows and matchings.)
440 The bad news is that computing the permanent is known to be~$\#P$-complete even
441 for zero-one matrices (as proven by Valiant in \cite{valiant:permanent}).
442 As a~ranking function for a~set of~matchings can be used to count all such
443 matchings, we obtain the following theorem:
446 If there is a~polynomial-time algorithm for lexicographic ranking of permutations with
447 a~set of restrictions which is a~part of the input, then $P=\#P$.
450 We will show that a~polynomial-time ranking algorithm would imply a~polynomial-time
451 algorithm for computing the permanent of an~arbitrary zero-one matrix, which
452 is a~$\#P$-complete problem.
454 We know from Lemma \ref{permchar} that non-zero
455 summands in the permanent of a~zero-one matrix~$M$ correspond to permutations restricted
456 by a~graph~$G$ whose bipartite adjacency matrix is~$M$. The permanent is
457 therefore equal to the number of such permutations, which is one more than the
458 rank of the lexicographically maximum such permutation.
459 It therefore remains to show that we can find the lexicographically maximum
460 permutation permitted by~$G$ in polynomial time.
462 We can determine $\pi[1]$ by trying all the possible values permitted by~$G$
463 in decreasing order and stopping as soon as we find~$\pi[1]$ which can be
464 extended to a~complete permutation. This can be verified using the previous
465 theorem on~the graph of the remaining restrictions, i.e., on~$G$ with the vertices
466 1~on one side and~$\pi[1]$ on the other side removed.
467 Once we have~$\pi[1]$, proceed by finding $\pi[2]$ in the same way, using the reduced
468 graph. This way we construct the whole maximum permutation~$\pi$
469 in~$\O(n^2)$ calls to the verification algorithm.
473 However, the hardness of computing the permanent is the only obstacle.
474 We will show that whenever we are given a~set of restrictions for which
475 the counting problem is easy (and it is also easy for subgraphs obtained
476 by deleting vertices), ranking is easy as well. The key will be once again
477 a~recursive structure, similar to the one we have seen in the case of plain
478 permutations in \ref{permrec}.
481 As we will work with permutations on different sets simultaneously, we have
482 to extend our notation accordingly. For every finite set of elements $A\subset{\bb N}$,
483 we will consider the set ${\cal P}_A$ of all permutations on~$A$ as customary
484 viewed as ordered $\vert A\vert$-tuples. The restriction graph will be represented
485 by its adjacency matrix~$M\in \{0,1\}^{\vert A\vert\times \vert A\vert}$ and
486 a~permutation $\pi\in{\cal P}_A$ satisfies~$M$ (conforms to the restrictions)
487 iff $M[i,j]=1$ whenever $j=R_A(\pi[i])+1$.\foot{The $+1$ is added because
488 matrices are indexed from~1 while the lowest rank is~0.}
489 The set of all such~$\pi$ will be denoted by~${\cal P}_{A,M}$
490 and their number (which obviously does not depend on the choice of~$A$) by $N_0(M) = {\per M}$.
492 We will also frequently need to delete a~row and a~column simultaneously
493 from~$M$. This operation corresponds to deletion of one vertex from each
494 part of the restriction graph. We will write $M^{i,j}$ for the matrix~$M$
495 with its $i$-th row and $j$-th column removed.
498 Let us consider a~permutation $\pi\in{\cal P}_A$ and $n=\vert A\vert$.
499 When we fix the value of the element $\pi[1]$, the remaining elements form
500 a~permutation $\pi'=\pi[2\ldots n]$ on the set~$A'=A\setminus\{\pi[1]\}$.
501 The permutation~$\pi$ satisfies the restriction matrix~$M$ if and only if
502 $M[1,a]=1$ for $a=R_A(\pi[1])$ and $\pi'$ satisfies a~restriction matrix~$M'=M^{1,a}$.
503 This translates to the following counterparts of algorithms \ref{rankalg}
507 $\<Rank>(\pi,i,n,A,M)$: Compute the lexicographic rank of a~permutation $\pi[i\ldots n]\in{\cal P}_{A,M}$.
510 \:If $i\ge n$, return 0.
512 \:$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$.
513 \cmt{$C_a$ is the number of permutations in ${\cal P}_{A,M}$ whose first element lies
514 among the first $a$ elements of~$A$.}
515 \:Return $b + \<Rank>(\pi,i+1,n,A\setminus\{\pi[i]\},M^{1,a+1})$.
518 \>To calculate the rank of~$\pi\in{\cal P}_{A,M}$, we call $\<Rank>(\pi,1,\vert A\vert,A,M)$.
521 $\<Unrank>(j,i,n,A,M)$: Return an~array~$\pi$ such that $\pi[i,\ldots,n]$ is the $j$-th
522 permutation in~${\cal P}_{A,M}$.
525 \:If $i>n$, return $(0,\ldots,0)$.
526 \:Find minimum $a$ such that $C_a > j$ (where $C_a$ is as above).
527 \:$x\=R^{-1}_A(a-1)$.
528 \:$\pi\=\<Unrank>(j-C_{a-1}, i+1, n, A\setminus\{x\}, M^{1,a})$.
533 \>To find the $j$-th permutation in~${\cal P}_{A,M}$, we call $\<Unrank>(j,1,\vert A\vert,A,M)$.
536 The time complexity of these algorithms will be dominated by the computation of
537 the numbers $C_a$, which requires a~linear amount of calls to~$N_0$ on every
538 level of the recursion, and by the manipulation with matrices. Because of this,
539 we do not any special data structure for the set~$A$, an~ordinary sorted array
540 will suffice. (Also, we cannot use the vector representation blindly, because
541 we have no guarantee that the word size is large enough.)
543 \thmn{Lexicographic ranking of restricted permutations}
544 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}$
545 and it is possible to calculate the permanent of~$M'$ in time $\O(t(n))$ for every matrix $M'$
546 obtained by deletion of rows and columns from~$M_n$. Then there exist algorithms
547 for ranking and unranking in ${\cal P}_{A,M_n}$ in time $\O(n^4 + n^2\cdot t(n))$
548 if $M_n$ and an~$n$-element set~$A$ are given as a~part of the input.
551 We will combine the algorithms \ref{rrankalg} and \ref{runrankalg} with the supplied
552 function for computing the permanent. All matrices constructed by the algorithm
553 are submatrices of~$M_n$ of the required type, so all computations of the function~$N_0$
554 can be performed in time $\O(t(n))$ each.
556 The recursion is $n$~levels deep. Every level involves
557 a~constant number of (un)ranking operations on~$A$ and computation of at most~$n$
558 of the $C_a$'s. Each such $C_a$ can be derived from~$C_{a-1}$ by constructing
559 a~submatrix of~$M$ (which takes $\O(n^2)$ time) and computing its $N_0$. We therefore
560 spend time $\O(n^2)$ on operations with the set~$A$, $\O(n^4)$ on matrix manipulations
561 and $\O(n^2\cdot t(n))$ by the computations of the~$N_0$'s.
564 %--------------------------------------------------------------------------------
566 \section{Hatcheck lady and other derangements}
568 The time bound for ranking of general restricted permutations shown in the previous
569 section is obviously very coarse. Its main purpose was to demonstrate that
570 many special cases of the ranking problem can be indeed computed in polynomial time.
571 For most families of restriction matrices, we can do much better. One of the possible improvements
572 is to replace the matrix~$M$ by the corresponding restriction graph and instead of
573 copying the matrix at every level of recursion, we perform local operations on the graph
574 and undo them later. Another useful trick is to calculate the $N_0$'s of the smaller
575 matrices using information already computed for the larger matrices.
577 These speedups are hard to state formally in general (they depend on the
578 structure of the matrices), so we will concentrate on a~specific example
579 instead. We will show that for the derangements one can achieve linear time complexity.
582 As we already know, the hatcheck permutations correspond to restriction
583 matrices which contain zeroes only on the main diagonal and graphs which are
584 complete bipartite with the matching $\{(i,i) : i\in[n]\}$ deleted. For
585 a~given order~$n$, we will call this matrix~$D_n$ and the graph~$G_n$ and
586 we will show that the submatrices of~$D_n$ share several nice properties:
588 \lemma\id{submatrixlemma}%
589 Let $D$ be a~submatrix of~$D_n$ obtained by deletion of rows and columns.
590 Then the value of the permanent of~$D$ depends only on the size of~$D$
591 and on the number of zero entries in~$D$.
594 We know from Lemma~\ref{permchar} that the permanent counts matchings in the
595 graph~$G$ obtained from~$G_n$ by removing the vertices corresponding to the
596 deleted rows and columns of~$D_n$. Therefore we can prove the lemma for
597 the number of matchings instead.
599 As~$G_n$ is a~complete bipartite graph without edges of a~single perfect matching,
600 the graph~$G$ must be also complete bipartite with some non-touching edges
601 missing. Two such graphs $G$ and~$G'$ are therefore isomorphic if and only if they have the
602 same number of vertices and also the same number of missing edges. As the
603 number of matchings is an~isomorphism invariant, the lemma follows.
607 There is a~clear combinatorial intuition behind this lemma: if we are
608 to count permutations with restrictions placed on~$z$ elements and these
609 restrictions are independent, it does not matter how exactly they look like.
612 Let $n_0(z,d)$ be the permanent shared by all submatrices as described
613 by the above lemma, which have $d\times d$ entries and exactly~$z$ zeroes.
616 The function~$n_0$ satisfies the following recurrence:
619 n_0(d,d) &= d! \cdot \sum\nolimits_{k=0}^d {(-1)^k \over k!}, \cr
621 n_0(z,d) &= z\cdot n_0(z-1,d-1) + (d-z)\cdot n_0(z,d-1) \quad\hbox{for $z<d$.} \cr
625 The base cases of the recurrence are straightforward: $n_0(0,d)$ counts the
626 unrestricted permutations on~$[d]$, and $n_0(d,d)$ is equal to the number of derangements
627 on~$[d]$, which we have already computed in Observation \ref{hatcheck}. Let us
628 prove the third formula.
630 We will count the permutations~$\pi$ restricted by a~matrix~$M$ of the given parameters
631 $z$ and~$d$. As $z<d$, there is at least one position in the permutation for which
632 no restriction applies and by Lemma~\ref{submatrixlemma} we can choose without
633 loss of generality that it is the first position.
635 If we select $\pi[1]$ from the~$z$ restricted elements, the rest of~$\pi$ is a~permutation
636 on the remaining elements with one restriction less and there are $n_0(z-1,d-1)$ such
637 permutations. On the other hand, if we use an~unrestricted element, all restrictions
638 stay in effect, so there are~$n_0(z,d-1)$ ways how to do so.
642 The function~$n_0$ also satisfies the following recurrence:
644 n_0(z-1,d) = n_0(z,d) + n_0(z-1,d-1) \quad\hbox{for $z>0$, $d>0$.} \eqno{(\maltese)}
648 We will again take advantage of having proven Lemma~\ref{submatrixlemma}, which
649 allows us to choose arbitrary matrices with the given parameters. Let us pick a~matrix~$M_z$
650 containing $z$~zeroes such that $M_z[1,1]=0$. Then define~$M_{z-1}$ which is equal to~$M_z$
651 everywhere except $M_{z-1}[1,1]=1$.
653 We will count the permutations $\pi\in {\cal P}_d$ satisfying~$M_{z-1}$ in two ways.
654 First, there are $n_0(z-1,d)$ such permutations. On the other hand, we can divide
655 the them to two types depending on whether $\pi[1]=1$. Those having $\pi[1]\ne 1$
656 are exactly the $n_0(z,d)$ permutations satisfying~$M_z$. The others correspond to
657 permutations $(\pi[2],\ldots,\pi[d])$ on $\{2,\ldots,d\}$ which satisfy~$M_z^{1,1}$,
658 so there are $n_0(z-1,d-1)$ of them.
661 \cor\id{nzeroprecalc}%
662 For a~given~$n$, a~table of the values $n_0(z,d)$ for all $0\le z\le d\le n$
663 can be precomputed in time~$\O(n^2)$.
666 Use either recurrence and induction on~$z+d$.
670 For every $0\le z<d$ we have $n_0(z,d) - n_0(z+1,d) \le n_0(z,d)/d$.
673 According to the recurrence $(\maltese)$, the difference $n_0(z,d) - n_0(z+1,d)$ is
674 equal to $n_0(z,d-1)$. We can bound this by plugging the trivial inequality $n_0(z,d-1) \le n_0(z-1,d-1)$
675 to~$(*)$, from which we obtain $n_0(z,d) \ge d\cdot n_0(z,d-1)$.
679 Let us show how to modify the ranking algorithm (\ref{rrankalg}) using the insight
680 we have gained into the structure of derangements.
682 The algorithm uses the matrix~$M$ only for computing~$N_0$ of its submatrices
683 and we have shown that this value depends only on the order of the matrix and
684 the number of zeroes in it. We will therefore replace maintenance of the matrix
685 by remember the number~$z$ of its zeroes and the set~$Z$ which contains the elements
686 $x\in A$ whose locations are restricted (there is a~zero anywhere in the $(R_A(x)+1)$-th
687 column of~$M$). In other words, every $x\in Z$ can appear at all positions in the
688 permutation except one (and these forbidden positions are different for different~$x$'s),
689 while the remaining elements of~$A$ can appear anywhere.
691 As we already observed (\ref{hatcheck}) that the number of derangements on~$[n]$ is $\Theta(n!)$,
692 we can again use word-sized vectors to represent the sets~$A$ and~$Z$ with insertion,
693 deletion, ranking and unranking on them in constant time.
695 When the algorithm selects a~submatrix $M'=M^{1,k}$ for an~element $x$ of~rank~$k-1$, this
696 matrix it is described by either by the choice of $z'=z-1$ and~$Z'=Z\setminus\{x\}$ (if $x\in Z$)
697 or $z'=z$ and $Z'=Z$ (if $x\not\in Z$).
698 All computations of~$N_0$ in the algorithm can therefore be replaced by looking
699 up the appropriate $n_0(z',\vert A\vert-1)$ in the precomputed table. Moreover, we can
700 calculate a~single~$C_a$ in constant time, because all summands are either $n_0(z,\vert A\vert-1)$
701 or $n_0(z-1,\vert A\vert-1)$ depending on the set~$Z$. We get:
702 $$C_a = r\cdot n_0(z-1,\vert A\vert-1) + (a-r) \cdot n_0(z,\vert A\vert-1),$$
703 where $r=R_Z(R^{-1}_A(a))$, that is the number of restricted elements among the $a$~smallest ones in~$A$.
705 All operations at a~single level of the \<Rank> function now run in constant time,
706 but \<Unrank> needs to search among the~$C_a$'s to find the first of them which
707 exceeds the given rank. We could use binary search, but that would take $\Theta(\log n)$
708 time. There is however a~clever trick: the value of~$C_a$ does not vary too much with
709 the set~$Z$. Specifically, by Corollary~\ref{smalldiff} the difference between the values
710 for $Z=\emptyset$ and $Z=A$ is at most $n_0(z-1,\vert A\vert -1)$. It is therefore
711 sufficient to just divide the rank by $n_0(z-1,\vert A\vert-1)$ and we get either
712 the correct value of~$a$ or one more. Both possibilities can be checked in constant time.
714 We can therefore conclude this section by the following theorem:
716 \thmn{Ranking of derangements}%
717 For every~$n$, the derangements on the set~$[n]$ can be ranked and unranked according to the
718 lexicographic order in time~$\O(n)$ after spending $\O(n^2)$ on initialization of auxiliary tables.
721 We modify the general algorithms for (un)ranking of restricted permutations (\ref{rrankalg} and \ref{runrankalg})
722 as described above (\ref{rrankmod}). Each of the $n$~levels of recursion will then run in constant time. The values~$n_0$ will
723 be looked up in a~table precalculated in quadratic time as shown in Corollary~\ref{nzeroprecalc}.