Publication

Abstract : A permutation on an alphabet Σ, is a sequence where every element in Σ occurs precisely once. Given a permutation π= (π1, π2, π3,....., πn) over the alphabet Σ ={0, 1, . . . , n−1 } the elements in two consecutive positions in π e.g. πi and πi+1 are said to form an emph{adjacency} if πi+1 =πi+1. The concept of adjacencies is widely used in computation. The set of permutations over Σ forms a symmetric group, that we call Pn. The identity permutation, In ∈ Pn where In =(0,1,2,...,n−1) has exactly n−1 adjacencies. Likewise, the reverse order permutation Rn(∈Pn)=(n−1, n−2, n−3, n−4, ...,0) has no adjacencies. We denote the set of permutations in Pn with exactly k adjacencies with Pn(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 Pn(k) i.e. ∀k∣Pn (k) ∣ for each type of adjacency in O(n2) time. Given a particular adjacency and the corresponding block-move, we show that ∀k∣Pn(k)∣ and the expected number of moves to sort a permutation in Pn are closely related. Consequently, we propose a model to estimate the expected number of moves to sort a permutation in Pn with a block-move. We show the results for prefix transposition. Due to symmetry, these results are also applicable to suffix transposition.