A permutation on an alphabet $ \Sigma $, is a sequence where every element in $ \Sigma $ occurs precisely once. Given a permutation $ \pi $= ($\pi_{ 1} $, $ \pi_{ 2} $, $ \pi_{ 3} $,....., $ \pi_{ n} $) over the alphabet $ \Sigma $ =$\{ $0, 1, . . . , n$-$1 $\}$ the elements in two consecutive positions in $ \pi $ e.g. $ \pi_{ i} $ and $ \pi_{ i+1} $ are said to form an \emph{ adjacency} if $ \pi_{ i+1} $ =$ \pi_{ i} $+1. The concept of adjacencies is widely used in computation. The set of permutations over $ \Sigma $ forms a symmetric group, that we call P$ _{ n} $. The identity permutation, I$ _{ n}$ $\in$ P$_{ n}$ where I$_{ n}$ =(0,1,2,...,n$-$1) has exactly n$ - $1 adjacencies. Likewise, the reverse order permutation R$_{ n} (\in P_{ n})$=(n$-$1, n$-$2, n$-$3, n$-$4, ...,0) has no adjacencies. We denote the set of permutations in P$_{ n} $ with exactly k adjacencies with P$_{ n} $(k). We study variations of adjacency. % A transposition exchanges adjacent sublists; when one of the sublists is restricted to be a prefix (suffix) then one obtains a prefix (suffix) transposition. We call the operations: transpositions, prefix transpositions and suffix transpositions as block-moves. A particular type of adjacency and a particular block-move are closely related. In this article we compute the cardinalities of P$_{ n}$(k) i.e. $ \forall_k \mid $P$ _{ n} $ (k) $ \mid $ for each type of adjacency in $O(n^2)$ time. Given a particular adjacency and the corresponding block-move, we show that $\forall_{ k} \mid P_{ n}(k)\mid$ and the expected number of moves to sort a permutation in P$_{ n} $ are closely related. Consequently, we propose a model to estimate the expected number of moves to sort a permutation in P$_{ n} $ with a block-move. We show the results for prefix transposition. Due to symmetry, these results are also applicable to suffix transposition.
Categories: cs.DM