Tighter upper bound for sorting permutations with prefix transpositions

摘要

Permutations are sequences where each symbol in the given alphabet Sigma 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 Sigma = {0, 1,...., n - 1} form a symmetric group, that we denote by P-n. The prefix transposition distance between two permutations pi* is an element of P-n and pi(similar to) is an element of P-n is the minimum number of prefix transpositions, also called moves, needed to transform pi* into pi(similar to). 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 pi* is an element of P-n to an arbitrary pi(similar to) is an element of P-n is equivalent to sorting some pi(boolean AND) is an element of P-n. Thus, upper bound for transforming any pi* is an element of P-n into any pi(similar to) is an element of P-n with prefix transpositions is simply the upper bound to sort any permutation pi is an element of P-n with moves. In the article that establishes the best known upper bound for prefix transposition distance over P-n as n - log(9/2) n, 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 - log(7/2) n for prefix transposition distance over P-n. (C) 2015 Published by Elsevier B.V.