On the number of pancake stacks requiring four flips to be sorted

zbMATH Open1437.05016arXiv1902.04055MaRDI QIDQ5207835FDOQ5207835

Authors: Saúl A. Blanco, Charles Buehrle, Akshay Patidar 

Publication date: 13 January 2020

Abstract: Using existing classification results for the 7- and 8-cycles in the pancake graph, we determine the number of permutations that require 4 pancake flips (prefix reversals) to be sorted. A similar characterization of the 8-cycles in the burnt pancake graph, due to the authors, is used to derive a formula for the number of signed permutations requiring 4 (burnt) pancake flips to be sorted. We furthermore provide an analogous characterization of the 9-cycles in the burnt pancake graph. Finally we present numerical evidence that polynomial formulae exist giving the number of signed permutations that require $k$ flips to be sorted, with $5leqkleq9$.

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

Recommendations

• On average and highest number of flips in pancake sorting
• On the problem of sorting burnt pancakes
• On the Diameter of the Pancake Network
• Polynomial-time sortable stacks of burnt pancakes
• Greedy flipping of pancakes and burnt pancakes

zbMATH Keywords

Cayley graphscycle embeddingpancake graphburnt pancake graph

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Graph theory (including graph drawing) in computer science (68R10) Exact enumeration problems, generating functions (05A15) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Paths and cycles (05C38)

Cited In (5)

• Some relations on prefix reversal generators of the symmetric and hyperoctahedral group
• Lengths of cycles in generalized pancake graphs
• An Algorithm to Enumerate Grid Signed Permutation Classes
• Some integer values in the spectra of burnt pancake graphs
• Polynomial-time sortable stacks of burnt pancakes

This page was built for publication: On the number of pancake stacks requiring four flips to be sorted

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