Sorting permutations by block-interchanges
✍ Scribed by David A. Christie
- Publisher
- Elsevier Science
- Year
- 1996
- Tongue
- English
- Weight
- 400 KB
- Volume
- 60
- Category
- Article
- ISSN
- 0020-0190
No coin nor oath required. For personal study only.
✦ Synopsis
Various global rearrangements of permutations, such as reversals and transpositions have recently become of interest because of their applications in genome analysis. The study of such rearrangements leads to computational problems that are of interest in their own right. In this paper we introduce an operation, called block-interchange, in which two substrings, or blocks, swap positions in the permutation. We demonstrate a polynomial-time algorithm for calculating the block-interchange distance of a permutation (i.e. the minimum number of block-interchanges required to transform the permutation to the identity). We also determine the block-interchange diameter of the symmetric group.