Prefix transpositions on binary and ternary strings

Abstract

The problem sorting by Prefix Transpositions asks for the minimum number of prefix transpositions required to sort the elements of a given permutation. In this thesis, we study a variant of this problem where the prefix transpositions act not on permutations but on strings over a fixed size alphabet. We determine the minimum number of prefix transpositions required to sort the binary and ternary strings, with polynomial time algorithms for these sorting problems. We also considered grouping and give polynomial-time algorithms for optimally grouping binary and ternary strings.