![Pancake sort operation](https://upload.wikimedia.org/wikipedia/commons/0/0f/Pancake_sort_operation.png)
Pancake sorting is the mathematical problem of sorting a disordered stack of pancakes in order of size when a
spatula
A spatula is a broad, flat, flexible blade used to mix, spread and lift material including foods, drugs, plaster and paints.
In medical applications, "spatula" may also be used synonymously with tongue depressor.
The word ''spatula'' derives f ...
can be inserted at any point in the stack and used to flip all pancakes above it. A ''pancake number'' is the minimum number of flips required for a given number of pancakes. In this form, the problem was first discussed by American geometer
Jacob E. Goodman. A variant of the problem is concerned with ''burnt'' pancakes, where each pancake has a burnt side and all pancakes must, in addition, end up with the burnt side on bottom.
All sorting methods require pairs of elements to be compared. For the traditional
sorting problem, the usual problem studied is to minimize the
number of comparisons required to sort a list. The number of actual operations, such as swapping two elements, is then irrelevant. For pancake sorting problems, in contrast, the aim is to minimize the number of operations, where the only allowed operations are reversals of the elements of some ''
prefix'' of the sequence. Now, the number of comparisons is irrelevant.
The pancake problems
The original pancake problem
The minimum number of flips required to sort any stack of pancakes has been shown to lie between and (approximately 1.07''n'' and 1.64''n'',) but the exact value is not known.
The simplest pancake sorting algorithm performs at most flips. In this algorithm, a kind of
selection sort
In computer science, selection sort is an in-place comparison sorting algorithm. It has an O(''n''2) time complexity, which makes it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is no ...
, we bring the largest pancake not yet sorted to the top with one flip; take it down to its final position with one more flip; and repeat this process for the remaining pancakes.
In 1979,
Bill Gates
William Henry Gates III (born October 28, 1955) is an American business magnate and philanthropist. He is a co-founder of Microsoft, along with his late childhood friend Paul Allen. During his career at Microsoft, Gates held the positions ...
and
Christos Papadimitriou
Christos Charilaos Papadimitriou ( el, Χρήστος Χαρίλαος "Χρίστος" Παπαδημητρίου; born August 16, 1949) is a Greek theoretical computer scientist and the Donovan Family Professor of Computer Science at Columbia Un ...
[ gave a lower bound of 1.06n flips and an upper bound of . The upper bound was improved, thirty years later, to by a team of researchers at the ]University of Texas at Dallas
The University of Texas at Dallas (UTD or UT Dallas) is a public research university in Richardson, Texas. It is one of the largest public universities in the Dallas area and the northernmost institution of the University of Texas system. It w ...
, led by Founders Professor Hal Sudborough.
In 2011, Laurent Bulteau, Guillaume Fertin, and Irena Rusu proved that the problem of finding the shortest sequence of flips for a given stack of pancakes is NP-hard, thereby answering a question that had been open for over three decades.
The burnt pancake problem
In a variation called the burnt pancake problem, the bottom of each pancake in the pile is burnt, and the sort must be completed with the burnt side of every pancake down. It is a ''signed permutation'', and if a pancake ''i'' is "burnt side up" a negative element ''i`'' is put in place of ''i'' in the permutation. In 2008, a group of undergraduates built a bacterial computer that can solve a simple example of the burnt pancake problem by programming '' E. coli'' to flip segments of DNA which are analogous to burnt pancakes. DNA has an orientation (5' and 3') and an order (promoter before coding). Even though the processing power expressed by DNA flips is low, the high number of bacteria in a culture provides a large parallel computing platform. The bacteria report when they have solved the problem by becoming antibiotic resistant.
The identical pancakes stack problem
This is inspired from the way Indian bread (roti
Roti (also known as chapati) is a round flatbread native to the Indian subcontinent. It is popular in India, Sri Lanka, Pakistan, Nepal, Bangladesh, Maldives, Myanmar, Malaysia, Indonesia, Singapore, Thailand, Guyana, Suriname, Jamaica, Trini ...
or chapati
Chapati (alternatively spelled chapatti, chappati, chapathi, or chappathi; pronounced as IAST: ), also known as ''roti'', ''rotli'', ''safati'', ''shabaati'', ''phulka'', (in East Africa) ''chapo'', (in Marathi) ''poli'', and (in the Maldives) ...
) is cooked. Initially, all rotis are stacked in one column, and the cook uses a spatula to flip the rotis so that each side of each roti touches the base fire at some point to toast. Several variants are possible: the rotis can be considered as single-sided or two-sided, and it may be forbidden or not to toast the same side twice. This version of the problem was first explored by Arka Roychowdhury.
The pancake problem on strings
The discussion above presumes that each pancake is unique, that is, the sequence on which the prefix reversals are performed is a ''permutation
In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or proc ...
''. However, "strings" are sequences in which a symbol can repeat, and this repetition may reduce the number of prefix reversals required to sort. Chitturi and Sudborough (2010) and Hurkens et al. (2007) independently showed that the complexity of transforming a compatible string into another with the minimum number of prefix reversals is NP-complete
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...
. They also gave bounds for the same. Hurkens et al. gave an exact algorithm to sort binary and ternary strings. Chitturi (2011) proved that the complexity of transforming a compatible signed string into another with the minimum number of signed prefix reversals—the burnt pancake problem on strings—is NP-complete.
History
The pancake sorting problem was first posed by Jacob E. Goodman, writing under the pseudonym "Harry Dweighter" ("harried waiter").
Although seen more often as an educational device, pancake sorting also appears in applications in parallel processor networks, in which it can provide an effective routing algorithm between processors.
The problem is notable as the topic of the only well-known mathematics paper by Microsoft
Microsoft Corporation is an American multinational technology corporation producing computer software, consumer electronics, personal computers, and related services headquartered at the Microsoft Redmond campus located in Redmond, Washing ...
founder Bill Gates
William Henry Gates III (born October 28, 1955) is an American business magnate and philanthropist. He is a co-founder of Microsoft, along with his late childhood friend Paul Allen. During his career at Microsoft, Gates held the positions ...
(as William Gates), entitled "Bounds for Sorting by Prefix Reversal" and co-authored with Christos Papadimitriou
Christos Charilaos Papadimitriou ( el, Χρήστος Χαρίλαος "Χρίστος" Παπαδημητρίου; born August 16, 1949) is a Greek theoretical computer scientist and the Donovan Family Professor of Computer Science at Columbia Un ...
. Published in 1979, it describes an efficient algorithm for pancake sorting. In addition, the most notable paper published by ''Futurama
''Futurama'' is an American animated science fiction sitcom created by Matt Groening for the Fox Broadcasting Company. The series follows the adventures of the professional slacker Philip J. Fry, who is cryogenically preserved for 1000 years a ...
'' co-creator David X. Cohen (as David S. Cohen), co-authored with Manuel Blum
Manuel Blum (born 26 April 1938) is a Venezuelan-American computer scientist who received the Turing Award in 1995 "In recognition of his contributions to the foundations of computational complexity theory and its application to cryptography and ...
, concerned the burnt pancake problem.
The connected problems of signed sorting by reversals and sorting by reversals were also studied more recently. Whereas efficient exact algorithms have been found for the signed sorting by reversals, the problem of sorting by reversals has been proven to be hard even to approximate to within certain constant factor, and also proven to be approximable in polynomial time to within the approximation factor 1.375.
Pancake graphs
An ''n''-pancake graph is a graph whose vertices are the permutations of ''n'' symbols from 1 to ''n'' and its edges are given between permutations transitive by prefix reversals. It is a regular graph
In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree o ...
with n! vertices, its degree is n−1. The pancake sorting problem and the problem to obtain the diameter
In geometry, a diameter of a circle is any straight line segment that passes through the center of the circle and whose endpoints lie on the circle. It can also be defined as the longest chord of the circle. Both definitions are also valid for ...
of the pancake graph is equivalent.
The pancake graph of dimension ''n'', Pn can be constructed recursively from n copies of Pn−1, by assigning a different element from the set as a suffix to each copy.
Their girth
Girth may refer to:
;Mathematics
* Girth (functional analysis), the length of the shortest centrally symmetric simple closed curve on the unit sphere of a Banach space
* Girth (geometry), the perimeter of a parallel projection of a shape
* Girth ...
:
:.
The γ(Pn) genus
Genus ( plural genera ) is a taxonomic rank used in the biological classification of extant taxon, living and fossil organisms as well as Virus classification#ICTV classification, viruses. In the hierarchy of biological classification, genus com ...
of Pn is:
:
Since pancake graphs have many interesting properties such as symmetric and recursive structures, small degrees and diameters compared against the size of the graph, much attention is paid to them as a model of interconnection networks for parallel computers. When we regard the pancake graphs as the model of the interconnection networks, the diameter of the graph is a measure that represents the delay of communication.
The pancake graphs are Cayley graph
In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem (named after Arthur Cayle ...
s (thus are vertex-transitive
In geometry, a polytope (e.g. a polygon or polyhedron) or a tiling is isogonal or vertex-transitive if all its vertices are equivalent under the symmetries of the figure. This implies that each vertex is surrounded by the same kinds of face in ...
) and are especially attractive for parallel processing. They have sublogarithmic degree and diameter, and are relatively sparse (compared to e.g. hypercubes
In geometry, a hypercube is an ''n''-dimensional analogue of a square () and a cube (). It is a closed, compact, convex figure whose 1-skeleton consists of groups of opposite parallel line segments aligned in each of the space's dimensions, perp ...
).
Algorithm
An example of the pancake sorting algorithm is given below in Python
Python may refer to:
Snakes
* Pythonidae, a family of nonvenomous snakes found in Africa, Asia, and Australia
** ''Python'' (genus), a genus of Pythonidae found in Africa and Asia
* Python (mythology), a mythical serpent
Computing
* Python (pro ...
. The code is similar to bubble sort
Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the input list element by element, comparing the current element with the one after it, swapping their values if needed. These passes ...
or selection sort
In computer science, selection sort is an in-place comparison sorting algorithm. It has an O(''n''2) time complexity, which makes it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is no ...
.
def flip(arr, k: int) -> None:
left = 0
while left < k:
arreft
A newt is a salamander in the subfamily Pleurodelinae. The terrestrial juvenile phase is called an eft. Unlike other members of the family Salamandridae, newts are semiaquatic, alternating between aquatic and terrestrial habitats. Not all aqu ...
arr = arr arreft
A newt is a salamander in the subfamily Pleurodelinae. The terrestrial juvenile phase is called an eft. Unlike other members of the family Salamandridae, newts are semiaquatic, alternating between aquatic and terrestrial habitats. Not all aqu ...
k -= 1
left += 1
def max_index(arr, k: int) -> int:
index = 0
for i in range(k):
if arr > arr ndex
index = i
return index
def pancake_sort(arr) -> None:
n = len(arr)
while n > 1:
maxdex = max_index(arr, n)
flip(arr, maxdex)
flip(arr, n - 1)
n -= 1
arreglo = 5, 8, 9, 1, 78, 30, 69, 4, 10pancake_sort(arreglo)
print(arreglo)
Related integer sequences
:
Sequences from The Online Encyclopedia of Integer Sequences:
* – maximum number of flips
* – number of stacks requiring the maximum number of flips (above)
* – maximum number of flips for a "burnt" stack
* – the number of flips for a sorted "burnt-side-on-top" stack
* – the above triangle, read by rows
References
Further reading
*
*
*
*
*
External links
Cut-the-Knot: Flipping pancakes puzzle
including a Java applet for the pancake problem and some discussion.
*
Animation explaining the bacterial computer that can solve the burnt pancake problem.
"Tower1/Pancake Flip" by Arka. A game based on pancake problem principle
{{DEFAULTSORT:Pancake Sorting
Sorting algorithms
Pancakes
Articles with example Python (programming language) code