Sorting a Permutation by block moves

2008/06/17 by Miklós Bóna, Miklos Bona, Bona, Miklos +2
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #68R05 #Algorithms and Data Compression #Combinatorics (math.CO) #DNA and Biological Computing #FOS: Mathematics #Genome Rearrangement Algorithms #math.CO #msc:68R05

paper · pdf · doi:10.48550/arxiv.0806.2787

7 pages

arxiv created 2008/06/17 · openalex publication_date 2008/06/17 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We prove a lower and an upper bound on the number of block moves necessary to sort a permutation. We put our results in contrast with existing results on sorting by block transpositions, and raise some open questions.

Related

• An Upper Bound on the Number of Circular Transpositions to Sort a Permutation
• The Average Number of Block Interchanges Needed to Sort A Permutation and a recent result of Stanley
• On Sorting by Bounded Block Interchanges
• A simple framework on sorting permutations
• Permutations sortable by n-4 passes through a stack