Publication Type:

Journal Article


CoRR (2016)



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.

Cite this Research Publication

Dr. Bhadrachalam Chitturi and Krishnaveni K. S, “Adjacencies in Permutations”, CoRR, 2016.