From 2eb7de659ad40307694b7f264b2ba4a9ea204cba Mon Sep 17 00:00:00 2001
From: Martin Mares <mj@ucw.cz>
Date: Wed, 27 Feb 2008 20:40:34 +0100
Subject: [PATCH] Finished derangements.

---
 rank.tex | 52 +++++++++++++++++++++++++++++++++++++++++++---------
 1 file changed, 43 insertions(+), 9 deletions(-)

diff --git a/rank.tex b/rank.tex
index 8df70ca..60a3be2 100644
--- a/rank.tex
+++ b/rank.tex
@@ -648,7 +648,16 @@ permutations $(\pi[2],\ldots,\pi[d])$ on $\{2,\ldots,d\}$ which satisfy~$M_z^{1,
 so there are $n_0(z-1,d-1)$ of them.
 \qed
 
-\cor For every $0\le z<d$ we have $n_0(z,d) - n_0(z+1,d) \le n_0(z,d)/d$.
+\cor\id{nzeroprecalc}%
+For a~given~$n$, a~table of the values $n_0(z,d)$ for all $0\le z\le d\le n$
+can be precomputed in time~$\O(n^2)$.
+
+\proof
+Use either recurrence and induction on~$z+d$.
+\qed
+
+\cor\id{smalldiff}%
+For every $0\le z<d$ we have $n_0(z,d) - n_0(z+1,d) \le n_0(z,d)/d$.
 
 \proof
 According to the recurrence $(\maltese)$, the difference $n_0(z,d) - n_0(z+1,d)$ is
@@ -656,9 +665,14 @@ equal to $n_0(z,d-1)$. We can bound this by plugging the trivial inequality $n_0
 to~$(*)$, from which we obtain $n_0(z,d) \ge d\cdot n_0(z,d-1)$.
 \qed
 
-\para
-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
+\para\id{rrankmod}%
+Let us show how to modify the ranking algorithm (\ref{rrankalg}) using the insight
+we have gained into the structure of derangements.
+
+The algorithm uses the matrix~$M$ only for computing~$N_0$ of its submatrices
+and we have shown that this value depends only on the order of the matrix and
+the number of zeroes in it. We will therefore replace maintenance of the matrix
+by remember the number~$z$ of its zeroes 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),
@@ -668,16 +682,36 @@ As we already observed (\ref{hatcheck}) that the number of derangements on~$[n]$
 we can again use word-sized vectors to represent the sets~$A$ and~$Z$ with insertion,
 deletion, ranking and unranking on them in constant time.
 
-When the algorithm selects a~submatrix $M'=M^{1,k}$ for an~element $x$ of~rank~$k-1$, it 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$).
+When the algorithm selects a~submatrix $M'=M^{1,k}$ for an~element $x$ of~rank~$k-1$, this
+matrix it is described by either by the choice of $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
+up the appropriate $n_0(z',\vert A\vert-1)$ in the 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:
+or $n_0(z-1,\vert A\vert-1)$ depending on the set~$Z$. 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.
+All operations at a~single level of the \<Rank> function now run in constant time,
+but \<Unrank> needs to search among the~$C_a$'s to find the first of them which
+exceeds the given rank. We could use binary search, but that would take $\Theta(\log n)$
+time. There is however a~clever trick: the value of~$C_a$ does not vary too much with
+the set~$Z$. Specifically, by Corollary~\ref{smalldiff} the difference between the values
+for $Z=\emptyset$ and $Z=A$ is at most $n_0(z-1,\vert A\vert -1)$. It is therefore
+sufficient to just divide the rank by $n_0(z-1,\vert A\vert-1)$ and we get either
+the correct value of~$a$ or one more. Both possibilities can be checked in constant time.
+
+We can therefore conclude this section by the following theorem:
+
+\thmn{Ranking of derangements}%
+For every~$n$, the derangements on the set~$[n]$ can be ranked and unranked according to the
+lexicographic order in time~$\O(n)$ after spending $\O(n^2)$ on initialization of auxiliary tables.
+
+\proof
+We modify the general algorithms for (un)ranking of restricted permutations (\ref{rrankalg} and \ref{runrankalg})
+as described above (\ref{rrankmod}). Each of the $n$~levels of recursion will then run in constant time. The values~$n_0$ will
+be looked up in a~table precalculated in quadratic time as shown in Corollary~\ref{nzeroprecalc}.
+\qed
 
 
 
-- 
2.39.2