On the problem of sorting burnt pancakes.

*(English)*Zbl 0831.68029Summary: The “pancake problem” is a well-known open combinatorial problem that recently has been shown to have applications to parallel processing. Given a stack of \(n\) pancakes in arbitrary order, all of different sizes, the goal is to sort them into the size-ordered configuration having the largest pancake on the bottom and the smallest on top. The allowed sorting operation is a “spatula flip”, in which a spatula is inserted beneath any pancake, and all pancakes above the spatula are lifted and replaced in reverse order. The problem is to bound \(f(n)\), the minimum number of flips required in the worst case to sort a stack of \(n\) pancakes. Equivalently, we seek bounds on the number of prefix reversals necessary to sort a list of \(n\) elements. Bounds of \(17n/16\) and \((5n+5)/3\) were shown by Gates and Papadimitriou in 1979. In this paper, we consider a traditional variation of the problem in which the pancakes are two sided (one side is “burnt”), and must be sorted to the size- ordered configuration in which every pancake has its burnt side down. Let \(g(n)\) be the number of flips required to sort \(n\) “burnt pancakes”. We find that \(3n/2 \leq g(n) \leq 2n-2\), where the upper bound holds for \(n \geq 10\). We consider the conjecture that the most difficult case for sorting \(n\) burnt pancakes is \(-I_n\), the configuration having the pancakes in proper size order, but in which each individual pancake is upside down. We present an algorithm for sorting \(- I_n\) in \(23n/14 + c\) flips, where \(c\) is a small constant, thereby establishing a bound of \(g(n) \leq 23n/14 + c\) under the conjecture. Furthermore, the longstanding upper bound of \(f(n)\) is also improved to \(23n/14 + c\) under the conjecture.

##### MSC:

68P10 | Searching and sorting |

##### Keywords:

pancake problem
PDF
BibTeX
XML
Cite

\textit{D. S. Cohen} and \textit{M. Blum}, Discrete Appl. Math. 61, No. 2, 105--120 (1995; Zbl 0831.68029)

Full Text:
DOI

##### References:

[1] | Akers, S.; Krishnamurthy, B., A group theoretic model for symmetric interconnection networks, (), 216-223 |

[2] | Amer. math. monthly, 82, 1010, (1975) |

[3] | Gates, W.; Papadimitriou, C., Bounds for sorting by prefix reversal, Discrete math., 27, 47-57, (1979) · Zbl 0397.68062 |

[4] | M. Heydari and H. Sudborough, Private communication. |

[5] | Miller, Z.; Pritikin, D.; Sudborough, H., Bounded dilation maps of hypercubes into Cayley graphs on the symmetric group, (1992), unpublished manuscript · Zbl 0860.68079 |

[6] | Qiu, K.; Meijer, H.; Akl, S., Parallel routing and sorting on the pancake network, (), 360-371 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.