From b43c62436be05c28db5cb9326864d5f46ea23e93 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Fri, 22 Feb 2008 13:53:32 +0100 Subject: [PATCH] Corrections of the ranking chapter. --- PLAN | 1 + rank.tex | 122 ++++++++++++++++++++++++++++++------------------------- 2 files changed, 67 insertions(+), 56 deletions(-) diff --git a/PLAN b/PLAN index 9e1cb10..0c0851e 100644 --- a/PLAN +++ b/PLAN @@ -65,6 +65,7 @@ Models: Ranking: - the general perspective: is it only a technical trick? +- def. of ranking: do we need to write \prec explicitly? - move description of the ranking set to the chapter on models? - ranking of permutations on general sets, relationship with integer sorting diff --git a/rank.tex b/rank.tex index 6a9cbd8..2a62859 100644 --- a/rank.tex +++ b/rank.tex @@ -14,29 +14,29 @@ in the following way: \defn\id{rankdef}% Let~$C$ be a~set of objects and~$\prec$ a~linear order on~$C$. The \df{rank} $R_{C,\prec}(x)$ of an~element $x\in C$ is the number of elements $y\in C$ such that $y\prec x$. -When~$\prec$ is defined on some superset of~$C$, we naturally extend the rank -to elements outside~$C$. -We will call the function $R_{C,\prec}$ the \df{ranking function} for $C$ and~$\prec$ -and its inverse $R^{-1}_{C,\prec}$ the \df{unranking function}. When the set -and the order are clear from the context, we will use just~$R(x)$ and $R^{-1}(x)$. +We will call the function $R_{C,\prec}$ the \df{ranking function} for $C$ ordered by~$\prec$ +and its inverse $R^{-1}_{C,\prec}$ the \df{unranking function} for $C$ and~$\prec$. When the set +and the order are clear from the context, we will use plain~$R(x)$ and $R^{-1}(x)$. +Also, when $\prec$ is defined on a~superset~$C'$ of~$C$, we naturally extend $R_C(x)$ +to elements $x\in C'\setminus C$. \example Let us consider the set $C_k=\{\0,\1\}^k$ of all binary strings of length~$k$ ordered lexicographically. Then $R^{-1}(i)$ is the $i$-th smallest element of this set, that is the number~$i$ written in binary and padded to~$k$ digits (i.e., $\(i)_k$ in the notation of Section~\ref{bitsect}). Obviously, $R(x)$ is the integer whose binary -representation is~$x$. +representation is the string~$x$. \para In this chapter, we will investigate how to compute the ranking and unranking -functions on different sets efficiently. Usually, we will make use of the fact +functions for different sets efficiently. Usually, we will make use of the fact that the ranks (and hence the input and output of our algorithm) are large numbers, so we can use the integers of a~similar magnitude to represent non-trivial data structures. \para -Until the end of the chapter, we will always assume that we are working on the -Random Access Machine. +Until the end of the chapter, we will always assume that our model of computation +is the Random Access Machine (more specifically, the Word-RAM). %-------------------------------------------------------------------------------- @@ -51,10 +51,10 @@ Many other applications are surveyed by Critani et al.~in~\cite{critani:rau} and most cases, the time complexity of the whole algorithm is limited by the efficiency of the (un)ranking functions. -In most cases, the permutations are ranked according to their lexicographic order. +The permutations are usually ranked according to their lexicographic order. In fact, an~arbitrary order is often sufficient if the ranks are used solely -for indexing of arrays, but the lexicographic order has an~additional advantage -of a~nice structure allowing many additional operations on permutations to be +for indexing of arrays. The lexicographic order however has an~additional advantage +of a~nice structure, which allows various operations on permutations to be performed directly on their ranks. Na\"\i{}ve algorithms for lexicographic ranking require time $\Theta(n^2)$ in the @@ -77,9 +77,9 @@ RAM data structures, yields a~linear-time algorithm for lexicographic (un)ranking. \nota\id{brackets}% -We will view permutations on a~ordered set~$A\subseteq {\bb N}$ as ordered $\vert A\vert$-tuples +We will view permutations on a~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 for indexing of these tuples: $\pi=(\pi[1],\ldots,\pi[\vert A\vert])$. +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. @@ -90,22 +90,24 @@ elements $\pi[2], \ldots, \pi[n]$ form a~permutation on $[n]-\{\pi[1]\} = \{1,\l The lexicographic order of two permutations $\pi$ and~$\pi'$ on the original set is then determined by $\pi[1]$ and $\pi'[1]$ and only if these elements are equal, it is decided by the lexicographic comparison of permutations $(\pi[2],\ldots,\pi[n])$ and -$(\pi'[2],\ldots,\pi'[n])$. Therefore the rank of $\pi$ is $(\pi[1]-1)\cdot +$(\pi'[2],\ldots,\pi'[n])$. Moreover, for fixed~$\pi[1]$ all permutations on +the smaller set occur exactly once, so the rank of $\pi$ is $(\pi[1]-1)\cdot (n-1)!$ plus the rank of $(\pi[2],\ldots,\pi[n])$. This gives us a~reduction from (un)ranking of permutations on $[n]$ to (un)ranking of permutations on a $(n-1)$-element set, which suggests a straightforward algorithm, but unfortunately this set is different from $[n-1]$ and it even depends on the value of~$\pi[1]$. We could renumber the elements to get $[n-1]$, -but it would require linear time per iteration. Instead, we generalize the +but it would require linear time per iteration. To avoid this, we generalize the problem to permutations on subsets of $[n]$. For a permutation $\pi$ on a~set $A\subseteq [n]$ of size~$m$, similar reasoning gives a~simple formula: $$ L((\pi[1],\ldots,\pi[m]),A) = R_A(\pi[1]) \cdot (m-1)! + L((\pi[2],\ldots,\pi[m]), A\setminus\{\pi[1]\}), $$ -which uses the ranking function~$R_A$ for~$A$. This formula leads to the -following algorithms (a~similar formulation can be found for example in~\cite{knuth:sas}): +which uses the ranking function~$R_A$ for~$A$. This recursive formula immediately +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$. \id{rankalg} @@ -119,32 +121,33 @@ following algorithms (a~similar formulation can be found for example in~\cite{kn \>We can call $\(\pi,1,n,[n])$ for ranking on~$[n]$, i.e., to calculate $L(\pi,[n])$. -\alg $\(j,i,n,A)$: Fill $\pi[i,\ldots,n]$ with the $j$-th permutation on~$A$. +\alg $\(j,i,n,A)$: Return an~array~$\pi$ such that $\pi[i,\ldots,n]$ is the $j$-th permutation on~$A$. \id{unrankalg} \algo -\:If $i>n$, return immediately. +\: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$. +\:Return~$\pi$. \endalgo \>We can call $\(j,1,n,[n])$ for the unranking problem on~$[n]$, i.e., to get $L^{-1}(j,[n])$. \para The most time-consuming parts of the above algorithms are of course operations -on the set~$A$. If we use a~data structure of a~known time complexity, the complexity +on the set~$A$. If we store~$A$ in a~data structure of a~known time complexity, the complexity of the whole algorithm is easy to calculate: \lemma\id{ranklemma}% -Suppose that there is a~data structure maintaining a~subset of~$[n]$ under insertion -and deletion of single elements and ranking and unranking of elements, all in time -at most $t(n)$ per operation. Then lexicographic ranking and unranking of permutations -can be performed in time $\O(n\cdot t(n))$. +Suppose that there is a~data structure maintaining a~subset of~$[n]$ under a~sequence +of deletions, which supports ranking and unranking of elements, and that +the time complexity of a~single operation is at most~$t(n)$. +Then lexicographic ranking and unranking of permutations can be performed in time $\O(n\cdot t(n))$. \proof Let us analyse the above algorithms. The depth of the recursion is~$n$ and in each nested invokation of the recursive procedure we perform a~constant number of operations. -All of them are either trivial or factorials (which can be precomputed in~$\O(n)$ time) +All of them are either trivial, or calculations of factorials (which can be precomputed in~$\O(n)$ time), or operations on the data structure. \qed @@ -156,22 +159,11 @@ improves it to $t(n)=O(\log n/\log \log n)$. In fact, all these variants are equ to the classical algorithms based on inversion vectors, because at the time of processing~$\pi[i]$, the value of $R_A(\pi[i])$ is exactly the number of elements forming inversions with~$\pi[i]$. -If we relax the requirements on the data structure to allow ordering of elements -dependent on the history of the structure (i.e., on the sequence of deletes performed -so far), we can implement all three operations in time $\O(1)$. We store -the values in an array and we also keep an inverse permutation. Ranking is done by direct -indexing, unranking by indexing of the inverse permutation and deleting by swapping -the element with the last element. We can observe that although it no longer -gives the lexicographic order, the unranking function is still the inverse of the -ranking function (the sequence of deletes from~$A$ is the same in both functions), -so this leads to $\O(n)$-time ranking and unranking in a~non-lexicographic order. -This order is the same as the one used by Myrvold and Ruskey in~\cite{myrvold:rank}. - -However, for our purposes we need to keep the same order on~$A$ over the whole -course of the algorithm. We will make use of the representation of vectors -by integers on the RAM as developed in Section~\ref{bitsect}, but first of -all, we will note that the ranks are large numbers, so the word size of the machine -has to be large as well for them to fit: +\para +To obtain linear time complexity, we will make use of the representation of +vectors by integers on the RAM as developed in Section~\ref{bitsect}, but first +of all, we will make sure that the ranks are large numbers, so the word size of the +machine has to be large as well: \obs $\log n! = \Theta(n\log n)$, therefore the word size~$W$ must be~$\Omega(n\log n)$. @@ -180,34 +172,52 @@ $\log n! = \Theta(n\log n)$, therefore the word size~$W$ must be~$\Omega(n\log n 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$. \qed -\thmn{Ranking of permutations \cite{mm:rank}} When we order the permutations -on the set~$[n]$ lexicographically, both ranking and unranking can be performed on the -RAM in time~$\O(n)$. +\thmn{Lexicographic ranking of permutations \cite{mm:rank}} +When we order the permutations on the set~$[n]$ lexicographically, both ranking +and unranking can be performed on the RAM in time~$\O(n)$. \proof -We will store the elements of the set~$A$ as a~sorted vector. Each element has -$\O(\log n)$ bits, so the whole vector requires $\O(n\log n)$ bits, which by the +We will store the elements of the set~$A$ in a~sorted vector. Each element has +$\O(\log n)$ bits, so the whole vector takes $\O(n\log n)$ bits, which by the above observation fits in a~constant number of machine words. We know from Algorithm~\ref{vecops} that ranks can be calculated in constant time in such vectors and that insertions and deletions can be translated to ranks and masking. Unranking, that is indexing of the vector, is masking alone. -So we can apply the previous Lemma~\ref{ranklemma} with $t(n)=\O(1)$. +So we can apply the previous Lemma \ref{ranklemma} with $t(n)=\O(1)$. \qed +\rem +We can also easily derive the non-lexicographic linear-time algorithm of Myrvold +and Ruskey~\cite{myrvold:rank} from our algorithm. We will relax the requirements +on the data structure to allow order of elements dependent on the history of the +structure (i.e., on the sequence of deletes performed so far). We can observe that +although the algorithm no longer gives the lexicographic ranks, the unranking function +is still an~inverse of the ranking function, because the sequence of deletes +from~$A$ is the same when both ranking and unraking. + +The implementation of the relaxed structure is straightforward. We store the set~$A$ +in an~array~$\alpha$ and use the order of the elements in~$\alpha$ determine the +order on~$A$. We will also maintain an~``inverse'' array $\alpha^{-1}$ such that +$\alpha[\alpha^{-1}[x]]=x$ for every~$x\in A$. Ranking and unranking can be performed +by a~simple lookup in these arrays: $R_A(x)=\alpha^{-1}[x]$, $R^{-1}(i)=\alpha[i]$. +When we want to delete an~element, we exchange it with the last element in the +array~$\alpha$ and update~$\alpha^{-1}$ accordingly. + + %-------------------------------------------------------------------------------- \section{Ranking of {\secitfont k\/}-permutations} \id{kpranksect} -The technique from the previous section can be also generalized to ranking of -\df{$k$-permutations,} that is of ordered $k$-tuples drawn from the set~$[n]$, -again in lexicographic order. There are $n^{\underline k} = n\cdot(n-1)\cdot\ldots\cdot(n-k+1)$ +The technique from the previous section can be also generalized to lexicographic ranking of +\df{$k$-permutations,} that is of ordered $k$-tuples drawn from the set~$[n]$. +There are $n^{\underline k} = n\cdot(n-1)\cdot\ldots\cdot(n-k+1)$ such $k$-permutations and they have a~recursive structure similar to the one of the permutations. We will therefore use the same recursive scheme as before (algorithms \ref{rankalg} and \ref{unrankalg}), but we will modify the first step of both algorithms to stop after the first~$k$ iterations. We will also replace the number $(n-i)!$ of permutations on the remaining elements by the number of $(k-i)$-permutations on the same elements, -i.e., $(n-i)^{\underline{k-i}}$. As $(n-i)^{\underline{k-i}} = (n-i) \cdot (n-i-1)^{\underline{k-i-1}}$, +i.e., by $(n-i)^{\underline{k-i}}$. As $(n-i)^{\underline{k-i}} = (n-i) \cdot (n-i-1)^{\underline{k-i-1}}$, we can precalculate all these numbers in linear time. Unfortunately, the ranks of $k$-permutations can be much smaller, so we can no @@ -234,7 +244,7 @@ and $\log n^{\underline k} \ge (n/2)(\log n - 1) \ge (k/2)(\log n - 1)$. \para It remains to show how to translate the operations on~$A$ to operations on~$H$, again stored as a~sorted vector~${\bf h}$. Insertion to~$A$ correspond to -deletion in~$H$ and vice versa. The rank of any~$x\in[n]$ in~$A$ is $x$ minus +deletion from~$H$ and vice versa. The rank of any~$x\in[n]$ in~$A$ is $x$ minus the number of holes which are smaller than~$x$, therefore $R_A(x)=x-R_H(x)$. To calculate $R_H(x)$, we can again use the vector operation \ from Algorithm \ref{vecops}, this time on the vector~$\bf h$. @@ -256,7 +266,7 @@ get $g_3+1+2-b_3 = 4+1+2-1 = 6$. The vector~$\bf b$ can be updated in constant time whenever an~element is inserted to~$\bf h$. It is sufficient to shift the fields apart (we know that the position of the new element in~$\bf b$ is the same as in~$\bf h$), -set the new value using masking operations and decrease all higher fields +insert the new value using masking operations and decrease all higher fields by one in parallel by using a~single subtraction. Updates after deletions from~$\bf h$ are analogous. @@ -267,12 +277,12 @@ modified data structure, each of which works again in constant time. Therefore we have just proven the following theorem, which brings this section to a~happy ending: -\thmn{Ranking of $k$-permutations \cite{mm:rank}} +\thmn{Lexicographic ranking of $k$-permutations \cite{mm:rank}} When we order the $k$-per\-mu\-ta\-tions on the set~$[n]$ lexicographically, both ranking and unranking can be performed on the RAM in time~$\O(k)$. \proof -Modify Algorithms \ref{rankalg} and \ref{unrankalg} as described in this section. +We modify algorithms \ref{rankalg} and \ref{unrankalg} as described in this section. The modified data structure performs all required operations on the set~$A$ in constant time. The depth of the recursion is $\O(k)$ and we spend $\O(1)$ time at every level. The time bound follows. -- 2.39.5