OFFERED

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.

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

207

PROGRAMS

OFFERED

OFFERED

6

AMRITA

CAMPUSES

CAMPUSES

15

CONSTITUENT

SCHOOLS

SCHOOLS

A

GRADE BY

NAAC, MHRD

NAAC, MHRD

8^{th}

RANK(INDIA):

NIRF 2018

NIRF 2018

150^{+}

INTERNATIONAL

PARTNERS

PARTNERS