The Average Number of Block Interchanges Needed to Sort A Permutation and a recent result of Stanley

2008/11/05 by Miklós Bóna, Miklos Bona, Bona, Miklos +2
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Algorithms and Data Compression #Genome Rearrangement Algorithms #math.CO #msc:05A05 #msc:05A15

paper · pdf · doi:10.48550/arxiv.0811.0740

8 pages, 4 figures

arxiv created 2008/11/05 · arxiv updated 2009/12/01

Abstract

We use an interesting result of probabilistic flavor concerning the product of two permutations consisting of one cycle each to find an explicit formula for the average number of block interchanges needed to sort a permutation of length n.

Related

• Sorting a Permutation by block moves
• On Sorting by Bounded Block Interchanges
• How many pop-stacks does it take to sort a permutation?
• An Upper Bound on the Number of Circular Transpositions to Sort a Permutation
• A simple framework on sorting permutations