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 The corresponding lexicographic ranking and unranking functions will be denoted by~$L(\pi,A)$
84 and $L^{-1}(i,A)$ respectively.
87 Let us first observe that permutations have a simple recursive structure.
88 If we fix the first element $\pi[1]$ of a~permutation~$\pi$ on the set~$[n]$, the
89 elements $\pi[2], \ldots, \pi[n]$ form a~permutation on $[n]-\{\pi[1]\} = \{1,\ldots,\pi[1]-1,\pi[1]+1,\ldots,n\}$.
90 The lexicographic order of two permutations $\pi$ and~$\pi'$ on the original set is then determined
91 by $\pi[1]$ and $\pi'[1]$ and only if these elements are equal, it is decided
92 by the lexicographic comparison of permutations $(\pi[2],\ldots,\pi[n])$ and
93 $(\pi'[2],\ldots,\pi'[n])$. Moreover, for fixed~$\pi[1]$ all permutations on
94 the smaller set occur exactly once, so the rank of $\pi$ is $(\pi[1]-1)\cdot
95 (n-1)!$ plus the rank of $(\pi[2],\ldots,\pi[n])$.
97 This gives us a~reduction from (un)ranking of permutations on $[n]$ to (un)ranking
98 of permutations on a $(n-1)$-element set, which suggests a straightforward
99 algorithm, but unfortunately this set is different from $[n-1]$ and it even
100 depends on the value of~$\pi[1]$. We could renumber the elements to get $[n-1]$,
101 but it would require linear time per iteration. To avoid this, we generalize the
102 problem to permutations on subsets of $[n]$. For a permutation $\pi$ on a~set
103 $A\subseteq [n]$ of size~$m$, similar reasoning gives a~simple formula:
105 L((\pi[1],\ldots,\pi[m]),A) = R_A(\pi[1]) \cdot (m-1)! +
106 L((\pi[2],\ldots,\pi[m]), A\setminus\{\pi[1]\}),
108 which uses the ranking function~$R_A$ for~$A$. This recursive formula immediately
109 translates to the following recursive algorithms for both ranking and unranking
110 (described for example in \cite{knuth:sas}):
112 \alg $\<Rank>(\pi,i,n,A)$: Compute the rank of a~permutation $\pi[i\ldots n]$ on~$A$.
115 \:If $i\ge n$, return~0.
117 \:$b\=\<Rank>(\pi,i+1,n,A \setminus \{\pi[i]\})$.
118 \:Return $a\cdot(n-i)! + b$.
121 \>We can call $\<Rank>(\pi,1,n,[n])$ for ranking on~$[n]$, i.e., to calculate
124 \alg $\<Unrank>(j,i,n,A)$: Return an~array~$\pi$ such that $\pi[i,\ldots,n]$ is the $j$-th permutation on~$A$.
127 \:If $i>n$, return $(0,\ldots,0)$.
128 \:$a\=R^{-1}_A(\lfloor j/(n-i)! \rfloor)$.
129 \:$\pi\=\<Unrank>(j\bmod (n-i)!,i+1,n,A\setminus \{a\})$.
134 \>We can call $\<Unrank>(j,1,n,[n])$ for the unranking problem on~$[n]$, i.e., to get $L^{-1}(j,[n])$.
137 The most time-consuming parts of the above algorithms are of course operations
138 on the set~$A$. If we store~$A$ in a~data structure of a~known time complexity, the complexity
139 of the whole algorithm is easy to calculate:
141 \lemma\id{ranklemma}%
142 Suppose that there is a~data structure maintaining a~subset of~$[n]$ under a~sequence
143 of deletions, which supports ranking and unranking of elements, and that
144 the time complexity of a~single operation is at most~$t(n)$.
145 Then lexicographic ranking and unranking of permutations can be performed in time $\O(n\cdot t(n))$.
148 Let us analyse the above algorithms. The depth of the recursion is~$n$ and in each
149 nested invokation of the recursive procedure we perform a~constant number of operations.
150 All of them are either trivial, or calculations of factorials (which can be precomputed in~$\O(n)$ time),
151 or operations on the data structure.
155 If we store~$A$ in an~ordinary array, we have insertion and deletion in constant time,
156 but ranking and unranking in~$\O(n)$, so $t(n)=\O(n)$ and the algorithm is quadratic.
157 Binary search trees give $t(n)=\O(\log n)$. The data structure of Dietz \cite{dietz:oal}
158 improves it to $t(n)=O(\log n/\log \log n)$. In fact, all these variants are equivalent
159 to the classical algorithms based on inversion vectors, because at the time of processing~$\pi[i]$,
160 the value of $R_A(\pi[i])$ is exactly the number of elements forming inversions with~$\pi[i]$.
163 To obtain linear time complexity, we will make use of the representation of
164 vectors by integers on the RAM as developed in Section~\ref{bitsect}, but first
165 of all, we will make sure that the ranks are large numbers, so the word size of the
166 machine has to be large as well:
169 $\log n! = \Theta(n\log n)$, therefore the word size~$W$ must be~$\Omega(n\log n)$.
172 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$.
175 \thmn{Lexicographic ranking of permutations \cite{mm:rank}}
176 When we order the permutations on the set~$[n]$ lexicographically, both ranking
177 and unranking can be performed on the RAM in time~$\O(n)$.
180 We will store the elements of the set~$A$ in a~sorted vector. Each element has
181 $\O(\log n)$ bits, so the whole vector takes $\O(n\log n)$ bits, which by the
182 above observation fits in a~constant number of machine words. We know from
183 Algorithm~\ref{vecops} that ranks can be calculated in constant time in such
184 vectors and that insertions and deletions can be translated to ranks and
185 masking. Unranking, that is indexing of the vector, is masking alone.
186 So we can apply the previous Lemma \ref{ranklemma} with $t(n)=\O(1)$.
190 We can also easily derive the non-lexicographic linear-time algorithm of Myrvold
191 and Ruskey~\cite{myrvold:rank} from our algorithm. We will relax the requirements
192 on the data structure to allow order of elements dependent on the history of the
193 structure (i.e., on the sequence of deletes performed so far). We can observe that
194 although the algorithm no longer gives the lexicographic ranks, the unranking function
195 is still an~inverse of the ranking function, because the sequence of deletes
196 from~$A$ is the same when both ranking and unraking.
198 The implementation of the relaxed structure is straightforward. We store the set~$A$
199 in an~array~$\alpha$ and use the order of the elements in~$\alpha$ determine the
200 order on~$A$. We will also maintain an~``inverse'' array $\alpha^{-1}$ such that
201 $\alpha[\alpha^{-1}[x]]=x$ for every~$x\in A$. Ranking and unranking can be performed
202 by a~simple lookup in these arrays: $R_A(x)=\alpha^{-1}[x]$, $R^{-1}(i)=\alpha[i]$.
203 When we want to delete an~element, we exchange it with the last element in the
204 array~$\alpha$ and update~$\alpha^{-1}$ accordingly.
207 %--------------------------------------------------------------------------------
209 \section{Ranking of {\secitfont k\/}-permutations}
212 The technique from the previous section can be also generalized to lexicographic ranking of
213 \df{$k$-permutations,} that is of ordered $k$-tuples drawn from the set~$[n]$.
214 There are $n^{\underline k} = n\cdot(n-1)\cdot\ldots\cdot(n-k+1)$
215 such $k$-permutations and they have a~recursive structure similar to the one of
216 the permutations. We will therefore use the same recursive scheme as before
217 (algorithms \ref{rankalg} and \ref{unrankalg}), but we will modify the first step of both algorithms
218 to stop after the first~$k$ iterations. We will also replace the number $(n-i)!$
219 of permutations on the remaining elements by the number of $(k-i)$-permutations on the same elements,
220 i.e., by $(n-i)^{\underline{k-i}}$. As $(n-i)^{\underline{k-i}} = (n-i) \cdot (n-i-1)^{\underline{k-i-1}}$,
221 we can precalculate all these numbers in linear time.
223 Unfortunately, the ranks of $k$-permutations can be much smaller, so we can no
224 longer rely on the same data structure fitting in a constant number of word-sized integers.
225 For example, if $k=1$, the ranks are $\O(\log n)$-bit numbers, but the data
226 structure still requires $\Theta(n\log n)$ bits.
228 We do a minor side step by remembering the complement of~$A$ instead, that is
229 the set of the at most~$k$ elements we have already seen. We will call this set~$H$
230 (because it describes the ``holes'' in~$A$). Let us prove that $\Omega(k\log n)$ bits
231 are needed to represent the rank, so the vector representation of~$H$ fits in
232 a~constant number of words.
235 The number of $k$-permutations on~$[n]$ is $2^{\Omega(k\log n)}$.
238 We already know that there $n^{\underline k}$ such $k$-permutations. If $k\le n/2$,
239 then every term in the product is $n/2$ or more, so $\log n^{\underline k} \ge
240 k\cdot (\log n - 1)$. If $k\ge n/2$, then $n^{\underline k} \ge n^{\underline{\smash{n/2}}}$
241 and $\log n^{\underline k} \ge (n/2)(\log n - 1) \ge (k/2)(\log n - 1)$.
245 It remains to show how to translate the operations on~$A$ to operations on~$H$,
246 again stored as a~sorted vector~${\bf h}$. Insertion to~$A$ correspond to
247 deletion from~$H$ and vice versa. The rank of any~$x\in[n]$ in~$A$ is $x$ minus
248 the number of holes which are smaller than~$x$, therefore $R_A(x)=x-R_H(x)$.
249 To calculate $R_H(x)$, we can again use the vector operation \<Rank> from Algorithm \ref{vecops},
250 this time on the vector~$\bf h$.
252 The only operation we cannot translate directly is unranking in~$A$. We will
253 therefore define an~auxiliary vector~$\bf r$ of the same size as~$\bf h$
254 containing the ranks of the holes: $r_i=R_A(h_i)=h_i-R_H(h_i)=h_i-i$.
255 To find the $j$-th smallest element of~$A$, we locate the interval between
256 holes to which this element belongs: the interval is bordered from below by
257 a~hole~$h_i$ such that $i$ is the largest index satisfying~$r_i \le j$.
258 In other words, $i=\<Rank>(r,j+1)-1$. Finding the right element in the interval
259 is then easy: $R^{-1}_A(j) = h_i + 1 + j - r_i$.
262 If $A=\{2,5,6\}$ and $n=8$, then ${\bf h}=(1,3,4,7,8)$ and ${\bf r}
263 = (0,1,1,3,3)$. When we want to calculate $R^{-1}_A(2)$, we find $i=2$ and
264 the wanted element is $h_2+1+2-r_2 = 4+1+2-1 = 6$.
267 The vector~$\bf r$ can be updated in constant time whenever an~element is
268 inserted to~$\bf h$. It is sufficient to shift the fields apart (we know
269 that the position of the new element in~$\bf r$ is the same as in~$\bf h$),
270 insert the new value using masking operations and decrease all higher fields
271 by one in parallel by using a~single subtraction. Updates after deletions
272 from~$\bf h$ are analogous.
274 We have replaced all operations on~$A$ by the corresponding operations on the
275 modified data structure, each of which works again in constant time. Therefore
276 we have just proven the following theorem, which brings this section to
279 \thmn{Lexicographic ranking of $k$-permutations \cite{mm:rank}}
280 When we order the $k$-per\-mu\-ta\-tions on the set~$[n]$ lexicographically, both
281 ranking and unranking can be performed on the RAM in time~$\O(k)$.
284 We modify algorithms \ref{rankalg} and \ref{unrankalg} for $k$-permutations as
285 shown at the beginning of this section. We use the vectors $\bf h$ and~$\bf r$
286 described above as an~implicit representation of the set~$A$. The modified
287 algorithm uses recursion $k$~levels deep and as each operation on~$A$ can be
288 performed in~$\O(1)$ time using $\bf h$ and~$\bf r$, every level takes only
289 constant time. The time bound follows. \qed
291 %--------------------------------------------------------------------------------
293 \section{Hatcheck lady and other derangements}
295 Another interesting class of combinatorial objects which can be counted and
296 ranked are restricted permutations. An~archetypal member of this class are
297 permutations without a~fixed point, i.e., permutations~$\pi$ such that $\pi(i)\ne i$
298 for all~$i$. These are also called \df{derangements} or \df{hatcheck permutations.}\foot{%
299 As the story in~\cite{matnes:idm} goes, once upon a~time there was a~hatcheck lady who
300 was so confused that she was giving out the hats completely randomly. What is
301 the probability that none of the gentlemen receives his own hat?} We will present
302 a~general (un)ranking method for any class of restricted permutations and
303 derive a~linear-time algorithm for the derangements from it.
306 We will fix a~non-negative integer~$n$ and use ${\cal P}$ for the set of
307 all~permutations on~$[n]$.
310 A~\df{restriction graph} is a~bipartite graph~$G$ whose parts are two copies
311 of the set~$[n]$. A~permutation $\pi\in{\cal P}$ satisfies the restrictions
312 if for every~$i$, $(i,\pi(i))$ is an~edge of~$G$.
314 We will follow the path unthreaded by Kaplansky and Riordan
315 \cite{kaplansky:rooks} and charted by Stanley in \cite{stanley:econe}.
316 We will relate restricted permutations to placements of non-attacking
317 rooks on a~hollow chessboard.
320 Let~$n$ be a~non-negative integer. Then:
322 \:A~\df{board} is the grid $B=[n]\times [n]$. It consists of $n^2$ \df{squares.}
323 \:A~\df{trace} of a~permutation $\pi\in{\cal P}$ is the set of squares $T(\pi)=\{ (i,\pi(i)) ; i\in[n] \}$.
327 The traces of permutations (and thus the permutations themselves) correspond
328 exactly to placements of $n$ rooks at the board in a~way such that the rooks do
329 not attack each other (i.e., there is at most one rook in every row and
330 likewise in every column; as there are $n$~rooks, there must be exactly one in
331 every row and column). When speaking about \df{rook placements,} we will always
332 mean non-attacking placements.
334 Restricted permutations then correspond to placements of rooks on a~restricted board,
335 which we obtain by removing the squares corresponding to the non-edges of the restriction
339 Let~$H\subseteq B$ be any set of squares called \df{holes} in the board. Then:
341 \:$N_j$ denotes the number of placements of $n$~rooks on the board such that exactly~$j$ of the rooks
342 stand on holes. That is, $N_j := \#\{ \pi\in{\cal P}: \#(H\cup T(\pi)) = j \}$.
343 \:$r_k$ is the number of ways how to place $k$~rooks on the holes. In other words,
344 this is the number of $k$-element subsets of~$H$ such that no two elements share
345 a~common row or column.
346 \:$N$ is the generating function for the~$N_j$'s:
348 N(x) = \sum_{j\ge 0} N_j x^j.
350 As $N_j=0$ for $j>n$, the function is in fact a~finite polynomial.
353 \thmn{The number of restricted permutations, Stanley \cite{stanley:econe}}
354 The function~$N$ can be expressed in terms of the numbers~$r_k$ as:
356 N(x) = \sum_{k=0}^n r_k \cdot (n-k)! \cdot (x-1)^k.
360 It is sufficient to prove that the equality holds for all integer~$x$.
361 The $N(x)$ counts the ways of placing~$n$ rooks on the board and labeling
362 each of them which stands on a~hole with an~element of~$[x]$. The right-hand
363 side counts the same: We can obtain any such configuration by placing $k$~rooks
364 on~$H$ first, labeling them with elements of~$\{2,\ldots,x\}$, placing
365 additional $n-k$ rooks on the remaining rows and columns (there are $(n-k)!$ ways
366 how to do this) and labeling the new rooks standing on a~hole with~1.
370 When we substitute~$x=0$ in the above equality, we get a~formula for the
371 number of rook placements avoiding~$H$:
372 $$N_0 = N(0) = \sum_{k=0}^n (-1)^k \cdot (n-k)! \cdot r_k.$$
375 Let us apply this theory to the hatcheck lady problem. The set~$H$ of holes is the diagonal
376 of the board: $H=\{ (i,i) : i\in[n] \}$. When we want to place~$k$ rooks on the holes,
377 we can do that in $r_k={n\choose k}$ ways. By the previous corollary, the number of
380 N_0 = \sum_{k=0}^n (-1)^k \cdot (n-k)! \cdot {n\choose k}
381 = \sum_{k=0}^n (-1)^k \cdot {n!\over k!}
382 = n! \cdot \sum_{k=0}^n {(-1)^k\over k!}.
384 As the sum converges to~$1/e$ when $n$~approaches infinity, we know that the number
385 of derangements is asymptotically $n!/e$.
388 Restricted permutations (and thus rook placements) can be also equated with
389 matchings in the restriction graph~$G$. Let us recall that the bipartite
390 adjacency matrix of this graph corresponds to the board and zeroes in this
391 matrix are at the places of the holes. A~perfect matching in~$G$ then
392 corresponds to a~placement of $n$~rooks on the board.
394 This brings both good and bad news. The good news is that we can use the
395 plethora of known results on bipartite matchings. We can for example determine
396 whether a~permutation satistying a~given set of restrictions exists
397 by reducing the corresponding matching problem to finding a~maximum flow in a~suitable
398 unit-capacity network. The flow can be then found using the Dinic's algorithm
399 in time $\O(\sqrt{n}\cdot m)$ (see \cite{dinic:flow} for the algorithm,
400 \cite{even:dinic} for the time bound and \cite{schrijver} for more references
401 on flows and matchings), where $m$~is the number of edges in the network, which
402 is linear in the size of the graph~$G$, therefore at worst $\Theta(n^2)$.
404 The bad news is that computing the number of such matchings is equivalent
405 to computing a~permanent of the adjacency matrix of the graph~$G$ and permanents
406 are known to be~$\#P$-complete even for zero-one matrices (as proven by Valiant
407 in \cite{valiant:permanent}). As a~ranking function for a~set of~matchings
408 can be used to count all such matchings, we obtain the following theorem:
411 If there is a~polynomial-time algorithm for lexicographic ranking of permutations with
412 an~arbitrary set of restrictions (which is a~part of the input), then $P=\#P$.
415 We will show that such a~ranking algorithm would enable us to compute the permanent
416 of an~arbitrary zero-one matrix, which is a~$\#P$-complete problem. Let~$G$ be the
417 bipartite graph with the bipartite adjacency matrix equal to the given matrix.
418 The permanent of the matrix is then equal to the number of perfect matchings
419 in~$G$, which is one more than the rank of the lexicographically maximal perfect
420 matching in~$G$. As ranking of perfect matchings in~$G$ corresponds to ranking
421 of permutations restricted by~$G$, it remains to show that we can find the
422 lexicographically maximal permitted permutation in polynomial time.
424 We can determine $\pi[1]$ by trying all the possible values permitted by~$G$
425 in decreasing order and stopping as soon as we find~$\pi[1]$ which can be
426 extended to a~complete permutation. We can do this for example by using the
427 Dinic's algorithm as described above on~the graph of remaining restrictions
428 (i.e., $G$ with the vertices 1 and~$\pi[1]$ and removed together with the corresponding
429 edges). Once we have~$\pi[1]$, we can fix it and proceed by finding $\pi[2]$
430 in the same way, using the reduced graph. This way we construct the whole
431 maximal permutation~$\pi$ in~$\O(n^2)$ calls to the Dinic's algorithm.
435 However, the hardness of computing the permanent is the only obstacle.
436 We will show that whenever we are given a~set of restrictions for which
437 the counting problem is easy (and it is also easy for subgraphs obtained
438 by deleting vertices), ranking is easy as well. The key will be once again
439 a~recursive structure, similar to the one we have seen in the case of plain
440 permutations in \ref{permrec}.
443 As we will work with permutations on different sets simultaneously, we have
444 to extend our notation slightly. For every finite set of elements $A\subset{\bb N}$,
445 we will consider the set ${\cal P}_A$ of all permutations on~$A$, as usually
446 viewed as ordered $\vert A\vert$-tuples. The restriction graph will be represented
447 by its adjacency matrix~$M\in \{0,1\}^{\vert A\vert\times \vert A\vert}$ and
448 a~permutation $\pi\in{\cal P}_A$ satisfies~$M$ (conforms to the restrictions)
449 iff $M[i,j]=1$ whenever $j=R_A(\pi[i])+1$.\foot{The $+1$ is added because
450 matrices are indexed from~1, while the lowest rank is~0.}
451 The set of all such~$\pi$ will be denoted by~${\cal P}_{A,M}$
452 and their number (which obviously does not depend on~$A$) by $N_0(M)$.
454 We will also frequently need to delete a~row and a~column simultaneously
455 from~$M$. This operation corresponds to deletion of one vertex from each
456 part of the restriction graph. We will write $M^{i,j}$ for the matrix~$M$
457 with $i$-th row and $j$-th column removed.
460 Let us consider a~permutation $\pi\in{\cal P}_A$ and $n=\vert A\vert$.
461 When we fix the value of the element $\pi[1]$, the remaining elements form
462 a~permutation $\pi'=(\pi[2],\ldots,\pi[n])$ on the set~$A'=A\setminus\{\pi[1]\}$.
463 The permutation~$\pi$ satisfies the restriction matrix~$M$ if and only if
464 $M[1,a]=1$ for $a=R_A(\pi[1])$ and $\pi'$ satisfies a~restriction matrix~$M'=M^{1,a}$.
465 This translates to the following counterparts of algorithms \ref{rankalg}
469 $\<Rank>(\pi,i,n,A,M)$: Compute the lexicographic rank of a~permutation $\pi[i\ldots n]\in{\cal P}_{A,M}$.
472 \:If $i\ge n$, return 0.
474 \:$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$.
475 \cmt{$C_a$ is the number of permutations in ${\cal P}_{A,M}$ whose first element lies
476 among the first$a$ elements of~$A$.}
477 \:Return $b + \<Rank>(\pi,i+1,n,A\setminus\{\pi[i]\},M^{1,a})$.
480 \>To calculate the rank of~$\pi\in{\cal P}_{A,M}$, we call $\<Rank>(\pi,1,\vert A\vert,A,M)$.
483 $\<Unrank>(j,i,n,A,M)$: Return an~array~$\pi$ such that $\pi[i,\ldots,n]$ is the $j$-th
484 permutation in~${\cal P}_{A,M}$.
487 \:If $i>n$, return $(0,\ldots,0)$.
488 \:Find minimum $\ell$ such that $C_\ell > j$ (where $C_\ell$ is as above)
489 \:$a\=R^{-1}_A(\ell-1)$.
490 \:$\pi\=\<Unrank>(j-C_{\ell-1}, i+1, n, A\setminus\{a\}, M^{1,\ell})$.
495 \>To find the $j$-th permutation in~${\cal P}_{A,M}$, we call $\<Unrank>(j,1,\vert A\vert,A,M)$.
498 The time complexity of these algorithms will be dominated by the computation of
499 the numbers $C_a$, which requires a~linear amount of calls to~$N_0$ on every
500 level of the recursion, and by the manipulation with matrices. Because of this,
501 we do not any special data structure for the set~$A$, an~ordinary sorted array
502 will suffice. (Also, we cannot use the vector representation blindly, because
503 we have no guarantee that the word size is large enough.)
505 \thmn{Lexicographic ranking of restricted permutations}
506 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}$
507 and it is possible to calculate $N_0(M')$ in time $\O(t(n))$ for every matrix $M'$
508 obtained by deletion of rows and columns from~$M_n$. Then there exist algorithms
509 for ranking and unranking in ${\cal P}_{A,M_n}$ in time $\O(n^4 + n^2\cdot t(n))$
510 if $M_n$ and an~$n$-element set~$A$ are given as a~part of the input.
513 We will combine the algorithms \ref{rrankalg} and \ref{runrankalg} with the supplied
514 function for computing~$N_0$. The recursion is $n$~levels deep. Every level involves
515 a~constant number of (un)ranking operations on~$A$ and computation of at most~$n$
516 of the $C_a$'s. Each such $C_a$ can be derived from~$C_{a-1}$ by constructing
517 a~submatrix of~$M$ (which takes $\O(n^2)$ time) and computing its $N_0$. We therefore
518 spend time $\O(n^2)$ on operations with the set~$A$, $\O(n^4)$ on matrix manipulations
519 and $\O(n^2\cdot t(n))$ by the computations of the~$N_0$'s.
523 This time bound is of course very coarse, its main purpose was to demonstrate that
524 many special cases of the ranking problem can be indeed computed in polynomial time.
525 For most families of restriction matrices, we can improve the time complexity significantly,
526 for example by storing the matrix as a~graph and replacing the expensive copying of matrices
527 by local operations on the graph.
529 Instead of showing many little improvements for various restrictions, we will
530 concentrate on the case of derangements and show that it is possible to achieve
531 linear time complexity.
533 \examplen{Ranking of hatcheck permutations}\id{hatrank}%
534 As we already know, the hatcheck permutations (a.k.a.~derangements) correspond
535 to restriction matrices which contain zeroes only on the main diagonal. We will
536 call these matrices~$D_n$ and show that their submatrices have a~somewhat
540 If $D$ is a~submatrix of~$D_n$ obtained by deletion of rows and columns.
541 Then the value $N_0(D)$ depends only on $n$ and the number of zero
545 Let us note that if we exchange two rows or two columns of~$D$, the number $N_0(D)$ does not change.
546 If we swap the $i$-th and $j$-th row to get a~new matrix~$D'$, there is a~simple bijection
547 between the permutations permitted by~$D'$ and the permutations permitted by~$D$ --- it suffices
548 to swap the $i$-th and $j$-th element of the tuple. Similarly, swapping the $i$-th and $j$-th
549 column corresponds to exchanging the $i$-th and $j$-th smallest value in the tuple.
551 As the matrix $D_n$ contains exactly one zero in every row and column, the matrix
552 $D$ must contain at most one zero in every row and column. If it contains exactly $k$ zeroes,
553 we can therefore re-arrange it by row and column exchanges to the form in which the
554 zeroes are placed at the first~$k$ positions at the main diagonal. We therefore know
555 that $N_0(D)$ is the same as the~$N_0$ of this normalized matrix, which depends only on~$k$.