Publication

Abstract : Permutations are sequences where each symbol in the given alphabet σ appears exactly once. A transposition is an operation that exchanges two adjacent sublists in a permutation; if one of these sublists is restricted to be a prefix then one obtains a prefix transposition. Transpositions over permutations have applications in genome rearrangements and computer interconnection networks. The set of permutations with n symbols derived from the alphabet σ={0, 1, . . ., n-1} form a symmetric group, that we denote by Pinfn/inf. The prefix transposition distance between two permutations π* ∈ Pinfn/inf and π ∈Pinfn/inf is the minimum number of prefix transpositions, also called moves, needed to transform π* into π . A prefix transposition can be modeled by a permutation operation. A permutation is type of sequence and it is also an operation. The generators for prefix transposition operation are a subset of permutation operation. As a result, transforming an arbitrary π*∈Pinfn/inf to an arbitrary π ∈Pinfn/inf is equivalent to sorting some π^∈Pn. Thus, upper bound for transforming any π*∈Pinfn/inf into any π ∈Pinfn/inf with prefix transpositions is simply the upper bound to sort any permutation π∈Pinfn/inf with moves. In the article that establishes the best known upper bound for prefix transposition distance over Pinfn/inf as n-loginf9/2/infn, explicit proofs were not given for some cases. In this article, we provide the missing proofs, validating the stated upper bound. Furthermore, we establish an upper bound of n-loginf7/2/infn for prefix transposition distance over Pinfn/inf. © 2015 Published by Elsevier B.V.