From 6b72140d7176e85d682e6804582b057e48e7b0da Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Wed, 27 Feb 2008 21:04:42 +0100 Subject: [PATCH] Use \pi[x...y]. --- PLAN | 1 - rank.tex | 19 ++++++++++--------- 2 files changed, 10 insertions(+), 10 deletions(-) diff --git a/PLAN b/PLAN index 15b9160..432e52d 100644 --- a/PLAN +++ b/PLAN @@ -68,7 +68,6 @@ Ranking: - the general perspective: is it only a technical trick? - ranking of permutations on general sets, relationship with integer sorting - mention approximation of permanent -- use \pi[x...y] Notation: diff --git a/rank.tex b/rank.tex index 3005c42..5be516d 100644 --- a/rank.tex +++ b/rank.tex @@ -79,9 +79,10 @@ RAM data structures, yields a~linear-time algorithm for lexicographic \nota\id{brackets}% 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. +use square brackets to index these tuples: $\pi=(\pi[1],\ldots,\pi[\vert A\vert])$, +and sub-tuples: $\pi[i\ldots j] = (\pi[i],\ldots,\pi[j])$. +The lexicographic ranking and unranking functions for the permutations on~$A$ +will be denoted by~$L(\pi,A)$ and $L^{-1}(i,A)$ respectively. \obs\id{permrec}% Let us first observe that permutations have a simple recursive structure. @@ -89,10 +90,10 @@ If we fix the first element $\pi[1]$ of a~permutation~$\pi$ on the set~$[n]$, th elements $\pi[2], \ldots, \pi[n]$ form a~permutation on $[n]-\{\pi[1]\} = \{1,\ldots,\pi[1]-1,\pi[1]+1,\ldots,n\}$. 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])$. 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])$. +by the lexicographic comparison of permutations $\pi[2\ldots n]$ and $\pi'[2\ldots 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 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 @@ -121,7 +122,7 @@ translates to the following recursive algorithms for both ranking and unranking \>We can call $\(\pi,1,n,[n])$ for ranking on~$[n]$, i.e., to calculate $L(\pi,[n])$. -\alg $\(j,i,n,A)$: Return an~array~$\pi$ such that $\pi[i,\ldots,n]$ is 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 $(0,\ldots,0)$. @@ -496,7 +497,7 @@ with its $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]\}$. +a~permutation $\pi'=\pi[2\ldots 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} -- 2.39.5