The average number of block interchanges needed to sort a permutation and a recent result of Stanley

DOI10.1016/J.IPL.2009.04.019MaRDI QIDQ989529zbMATH OpenOpenAlexFDO

Authors Miklós Bóna, Ryan Flynn

Publication date 20 August 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0811.0740

zbMATH Keywords

permutationsanalysis of algorithmsprobabilitycyclessortingblock interchanges

Mathematics Subject Classification ID

Combinatorics in computer science (68R05)

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$.

Recommendations

• Sorting permutations by block-interchanges
• An improved block-interchange algorithm
• Data Exchange and Permutation Length
• The average order of a permutation
• On the average number of reversals needed to sort signed permutations

Cites work

• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• Inductive and injective proofs of log concavity results
• Introduction to enumerative combinatorics. With a foreword by Richard Stanley
• Nombre de représentations d'une permutation comme produit de deux cycles de longueurs données
• On Hultman numbers
• Sorting permutations by block-interchanges
• Two enumerative results on cycles of permutations

Cited in

(10)

• Separation probabilities for products of permutations
• Data Exchange and Permutation Length
• A versatile combinatorial approach of studying products of long cycles in symmetric groups
• An improved algorithm for sorting by block-interchanges based on permutation groups
• Approximation algorithms for sorting permutations by extreme block-interchanges
• On the average number of reversals needed to sort signed permutations
• On products of permutations with the most uncontaminated cycles by designated labels
• The distribution of cycles in breakpoint graphs of signed permutations
• On reduced unicellular hypermonopoles
• Plane permutations and applications to a result of Zagier-Stanley and distances of permutations

This page was built for publication: The average number of block interchanges needed to sort a permutation and a recent result of Stanley

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q989529)