Pancake sorting

Last updated

Demonstration of the primary operation. The spatula is flipping over the top three pancakes, with the result seen below. In the burnt pancake problem, their top sides would now be burnt instead of their bottom sides. Pancake sort operation.png
Demonstration of the primary operation. The spatula is flipping over the top three pancakes, with the result seen below. In the burnt pancake problem, their top sides would now be burnt instead of their bottom sides.

Pancake sorting is the mathematical problem of sorting a disordered stack of pancakes in order of size when a spatula 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. [1] 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.

Contents

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 n pancakes has been shown to lie between 15/14n and 18/11n (approximately 1.07n and 1.64n), but the exact value is not known. [2]

The simplest pancake sorting algorithm performs at most 2n− 3 flips. In this algorithm, a kind of selection sort, 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 and Christos Papadimitriou [3] gave a lower bound of 17/16n (approximately 1.06n) flips and an upper bound of (5n+5)/3. The upper bound was improved, thirty years later, to 18/11n by a team of researchers at the University of Texas at Dallas, led by Founders Professor Hal Sudborough. [4] [5]

In 2011, Laurent Bulteau, Guillaume Fertin, and Irena Rusu [6] 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. [7]

The identical pancakes stack problem

This is inspired from the way Indian bread (roti or chapati) 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. [8]

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 . 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. They also gave bounds for the same. Hurkens et al. gave an exact algorithm to sort binary and ternary strings. Chitturi [9] (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"). [10]

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. [11] [12]

The problem is notable as the topic of the only well-known mathematics paper by Microsoft founder Bill Gates (as William Gates), entitled "Bounds for Sorting by Prefix Reversal" and co-authored with Christos Papadimitriou. Published in 1979, it describes an efficient algorithm for pancake sorting. [3] In addition, the most notable paper published by Futurama co-creator David X. Cohen (as David S. Cohen), co-authored with Manuel Blum, concerned the burnt pancake problem. [13]

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, [14] the problem of sorting by reversals has been proven to be hard even to approximate to within certain constant factor, [15] and also proven to be approximable in polynomial time to within the approximation factor 1.375. [16]

Pancake graphs

The pancake graph P3 Pancake graph g3.svg
The pancake graph P3
The pancake graph P4 can be constructed recursively from 4 copies of P3 by assigning a different element from the set {1, 2, 3, 4} as a suffix to each copy. Pancake graph g4.svg
The pancake graph P4 can be constructed recursively from 4 copies of P3 by assigning a different element from the set {1, 2, 3, 4} as a suffix to each copy.

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 with n! vertices, its degree is n−1. The pancake sorting problem and the problem to obtain the diameter of the pancake graph is equivalent. [17]

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 {1, 2, …, n} as a suffix to each copy.

Their girth:

.

The γ(Pn) genus of Pn is: [18]

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. [19] [20] [21] 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. [22] [23]

The pancake graphs are Cayley graphs (thus are vertex-transitive) and are especially attractive for parallel processing. They have sublogarithmic degree and diameter, and are relatively sparse (compared to e.g. hypercubes). [18]

Algorithm

An example of the pancake sorting algorithm is given below in Python. The code is similar to bubble sort or selection sort. 

defflip(arr,k:int)->None:left=0whileleft<k:arr[left],arr[k]=arr[k],arr[left]k-=1left+=1defmax_index(arr,k:int)->int:index=0foriinrange(k):ifarr[i]>arr[index]:index=ireturnindexdefpancake_sort(arr)->None:n=len(arr)whilen>1:maxdex=max_index(arr,n)ifmaxdex!=n-1:ifmaxdex!=0:flip(arr,maxdex)flip(arr,n-1)n-=1arreglo=[15,8,9,1,78,30,69,4,10]pancake_sort(arreglo)print(arreglo)
Number of stacks of given height n that require unique flips k  to get sorted
Height
n		k
0123456789101112131415
11
211
31221
4136113
51412354820
61520791992811332
7163014954313571903101635
817422511191428110561150118520455
918563912278106663801593585132697793795804
101972575396322825106461377863919365130975681467873232
11110908096429438912527371174766412651599810731425047191236489563546
1211111010999883779375333973064788141419294933725211842004316933221311105006613032704167
1311213214511455613009610305057046321403095551849922756397834751525125357218305656614586536481868748522001

Sequences from The Online Encyclopedia of Integer Sequences:

Related Research Articles

A distributed system is a system whose components are located on different networked computers, which communicate and coordinate their actions by passing messages to one another. Distributed computing is a field of computer science that studies distributed systems.

<span class="mw-page-title-main">Minimum spanning tree</span> Least-weight tree connecting graph vertices

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible. More generally, any edge-weighted undirected graph has a minimum spanning forest, which is a union of the minimum spanning trees for its connected components.

The Hamiltonian path problem is a topic discussed in the fields of complexity theory and graph theory. It decides if a directed or undirected graph, G, contains a Hamiltonian path, a path that visits every vertex in the graph exactly once. The problem may specify the start and end of the path, in which case the starting vertex s and ending vertex t must be identified.

<span class="mw-page-title-main">Strongly connected component</span> Partition of a graph whose components are reachable from all vertices

In the mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachable from every other vertex. The strongly connected components of an arbitrary directed graph form a partition into subgraphs that are themselves strongly connected. It is possible to test the strong connectivity of a graph, or to find its strongly connected components, in linear time (that is, Θ(V + E)).

In computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge (u,v) from vertex u to vertex v, u comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks. Precisely, a topological sort is a graph traversal in which each node v is visited only after all its dependencies are visited. A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG). Any DAG has at least one topological ordering, and algorithms are known for constructing a topological ordering of any DAG in linear time. Topological sorting has many applications, especially in ranking problems such as feedback arc set. Topological sorting is possible even when the DAG has disconnected components.

<span class="mw-page-title-main">Christos Papadimitriou</span> Greek computer scientist (b. 1949)

Christos Charilaos Papadimitriou is a Greek theoretical computer scientist and the Donovan Family Professor of Computer Science at Columbia University.

In graph theory, a path decomposition of a graph G is, informally, a representation of G as a "thickened" path graph, and the pathwidth of G is a number that measures how much the path was thickened to form G. More formally, a path-decomposition is a sequence of subsets of vertices of G such that the endpoints of each edge appear in one of the subsets and such that each vertex appears in a contiguous subsequence of the subsets, and the pathwidth is one less than the size of the largest set in such a decomposition. Pathwidth is also known as interval thickness, vertex separation number, or node searching number.

<span class="mw-page-title-main">Permutation graph</span> Graph representing a permutation

In the mathematical field of graph theory, a permutation graph is a graph whose vertices represent the elements of a permutation, and whose edges represent pairs of elements that are reversed by the permutation. Permutation graphs may also be defined geometrically, as the intersection graphs of line segments whose endpoints lie on two parallel lines. Different permutations may give rise to the same permutation graph; a given graph has a unique representation if it is prime with respect to the modular decomposition.

<span class="mw-page-title-main">Trivially perfect graph</span> Graph where every connected induced subgraph has a universal vertex

In graph theory, a trivially perfect graph is a graph with the property that in each of its induced subgraphs the size of the maximum independent set equals the number of maximal cliques. Trivially perfect graphs were first studied by but were named by Golumbic (1978); Golumbic writes that "the name was chosen since it is trivial to show that such a graph is perfect." Trivially perfect graphs are also known as comparability graphs of trees, arborescent comparability graphs, and quasi-threshold graphs.

<span class="mw-page-title-main">Inversion (discrete mathematics)</span> Pair of positions in a sequence where two elements are out of sorted order

In computer science and discrete mathematics, an inversion in a sequence is a pair of elements that are out of their natural order.

In computer science, the all nearest smaller values problem is the following task: for each position in a sequence of numbers, search among the previous positions for the last position that contains a smaller value. This problem can be solved efficiently both by parallel and non-parallel algorithms: Berkman, Schieber & Vishkin (1993), who first identified the procedure as a useful subroutine for other parallel programs, developed efficient algorithms to solve it in the Parallel Random Access Machine model; it may also be solved in linear time on a non-parallel computer using a stack-based algorithm. Later researchers have studied algorithms to solve it in other models of parallel computation.

<span class="mw-page-title-main">Separable permutation</span>

In combinatorial mathematics, a separable permutation is a permutation that can be obtained from the trivial permutation 1 by direct sums and skew sums. Separable permutations may be characterized by the forbidden permutation patterns 2413 and 3142; they are also the permutations whose permutation graphs are cographs and the permutations that realize the series-parallel partial orders. It is possible to test in polynomial time whether a given separable permutation is a pattern in a larger permutation, or to find the longest common subpattern of two separable permutations.

In combinatorial mathematics and theoretical computer science, a permutation pattern is a sub-permutation of a longer permutation. Any permutation may be written in one-line notation as a sequence of digits representing the result of applying the permutation to the digit sequence 123...; for instance the digit sequence 213 represents the permutation on three elements that swaps elements 1 and 2. If π and σ are two permutations represented in this way, then π is said to contain σ as a pattern if some subsequence of the digits of π has the same relative order as all of the digits of σ.

In the mathematics of paper folding, map folding and stamp folding are two problems of counting the number of ways that a piece of paper can be folded. In the stamp folding problem, the paper is a strip of stamps with creases between them, and the folds must lie on the creases. In the map folding problem, the paper is a map, divided by creases into rectangles, and the folds must again lie only along these creases.

In mathematics and computer science, a stack-sortable permutation is a permutation whose elements may be sorted by an algorithm whose internal storage is limited to a single stack data structure. The stack-sortable permutations are exactly the permutations that do not contain the permutation pattern 231; they are counted by the Catalan numbers, and may be placed in bijection with many other combinatorial objects with the same counting function including Dyck paths and binary trees.

<span class="mw-page-title-main">Superpermutation</span> String in combinatorial math

In combinatorial mathematics, a superpermutation on n symbols is a string that contains each permutation of n symbols as a substring. While trivial superpermutations can simply be made up of every permutation concatenated together, superpermutations can also be shorter because overlap is allowed. For instance, in the case of n = 2, the superpermutation 1221 contains all possible permutations, but the shorter string 121 also contains both permutations.

<span class="mw-page-title-main">Pancake graph</span>

In the mathematical field of graph theory, the pancake graphPn or 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.

In mathematics and computer science, the sorting numbers are a sequence of numbers introduced in 1950 by Hugo Steinhaus for the analysis of comparison sort algorithms. These numbers give the worst-case number of comparisons used by both binary insertion sort and merge sort. However, there are other algorithms that use fewer comparisons.

<span class="mw-page-title-main">Topswops</span>

Topswops are mathematical problems devised and analysed by the British mathematician John Conway in 1973. Contrary to other games and problems introduced by Conway, these problems have not received much attention from the scientific community. Two famous mathematicians who have contributed to the problem are Martin Gardner and Donald Knuth.

References

  1. ↑ Singh, Simon (November 14, 2013). "Flipping pancakes with mathematics". The Guardian . Retrieved March 25, 2014.
  2. ↑ Fertin, G.; Labarre, A.; Rusu, I.; Tannier, E.; Vialette, S. (2009). Combinatorics of Genome Rearrangements. The MIT Press. ISBN   9780262062824.
  3. 1 2 Gates, W.; Papadimitriou, C. (1979). "Bounds for Sorting by Prefix Reversal". Discrete Mathematics . 27: 47–57. doi: 10.1016/0012-365X(79)90068-2 .
  4. ↑ "Team Bests Young Bill Gates With Improved Answer to So-Called Pancake Problem in Mathematics". University of Texas at Dallas News Center. September 17, 2008. Archived from the original on February 14, 2012. Retrieved November 10, 2008. A team of UT Dallas computer science students and their faculty adviser have improved upon a longstanding solution to a mathematical conundrum known as the pancake problem. The previous best solution, which stood for almost 30 years, was devised by Bill Gates and one of his Harvard instructors, Christos Papadimitriou, several years before Microsoft was established.
  5. ↑ Chitturi, B.; Fahle, W.; Meng, Z.; Morales, L.; Shields, C. O.; Sudborough, I. H.; Voit, W. (August 31, 2009). "An (18/11)n upper bound for sorting by prefix reversals". Theoretical Computer Science. Graphs, Games and Computation: Dedicated to Professor Burkhard Monien on the Occasion of his 65th Birthday. 410 (36): 3372–3390. doi: 10.1016/j.tcs.2008.04.045 .
  6. ↑ Bulteau, Laurent; Fertin, Guillaume; Rusu, Irena (2015). "Pancake Flipping Is Hard". Journal of Computer and System Sciences. 81 (8): 1556–1574. arXiv: 1111.0434 . doi:10.1016/j.jcss.2015.02.003.
  7. ↑ Haynes, Karmella A; Broderick, Marian L; Brown, Adam D; Butner, Trevor L; Dickson, James O; Harden, W Lance; Heard, Lane H; Jessen, Eric L; Malloy, Kelly J; Ogden, Brad J; Rosemond, Sabriya; Simpson, Samantha; Zwack, Erin; Campbell, A Malcolm; Eckdahl, Todd T; Heyer, Laurie J; Poet, Jeffrey L (2008). "Engineering bacteria to solve the Burnt Pancake Problem". Journal of Biological Engineering. 2: 8. doi: 10.1186/1754-1611-2-8 . PMC   2427008 . PMID   18492232.
  8. ↑ Roychowdhury, Arka (March 18, 2015). "Itunes: Flipping Pancakes". Crazy1S.
  9. ↑ Chitturi, Bhadrachalam (2011). "A Note on Complexity of Genetic Mutations". Discrete Mathematics, Algorithms and Applications. 03 (3): 269–286. doi:10.1142/S1793830911001206.
  10. ↑ Dweighter, Harry (1975), "Elementary Problem E2569", Amer. Math. Monthly, 82 (10): 1009–1010, doi:10.2307/2318260, JSTOR   2318260
  11. ↑ Gargano, L.; Vaccaro, U.; Vozella, A. (1993). "Fault tolerant routing in the star and pancake interconnection networks". Information Processing Letters. 45 (6): 315–320. CiteSeerX   10.1.1.35.9056 . doi:10.1016/0020-0190(93)90043-9. MR   1216942..
  12. ↑ Kaneko, K.; Peng, S. (2006). "Disjoint paths routing in pancake graphs". Proceedings of Seventh International Conference on Parallel and Distributed Computing, Applications and Technologies, 2006 (PDCAT '06). pp. 254–259. doi:10.1109/PDCAT.2006.56. ISBN   978-0-7695-2736-9. S2CID   18777751..
  13. ↑ Cohen, D.S.; Blum, M. (1995). "On the problem of sorting burnt pancakes". Discrete Applied Mathematics. 61 (2): 105. doi: 10.1016/0166-218X(94)00009-3 .
  14. ↑ Kaplan, H.; Shamir, R.; Tarjan, R.E. (1997). "Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals". Proc. 8th ACM-SIAM SODA: 178–87.
  15. ↑ Berman, P.; Karpinski, M. (1999). "On Some Tighter Inapproximability Results". Proc. 26th ICALP (1999). Lecture Notes in Computer Science. 1644: 200–09.
  16. ↑ Berman, P.; Karpinski, M.; Hannenhalli, S. (2002). "1.375-Approximation Algorithms for Sorting by Reversals". Proc. 10th ESA (2002). Lecture Notes in Computer Science. 2461: 200–10.
  17. ↑ Asai, Shogo; Kounoike, Yuusuke; Shinano, Yuji; Kaneko, Keiichi (September 1, 2006). "Computing the Diameter of 17-Pancake Graph Using a PC Cluster". Euro-Par 2006 Parallel Processing. Lecture Notes in Computer Science. Vol. 4128. pp. 1114–1124. doi:10.1007/11823285_117. ISBN   978-3-540-37783-2.{{cite book}}: |journal= ignored (help)
  18. 1 2 Nguyen, Quan; Bettayeb, Said (November 5, 2009). "On the Genus of Pancake Network" (PDF). The International Arab Journal of Information Technology. 8 (3): 289–292.
  19. ↑ Akl, S.G.; Qiu, K.; Stojmenović, I. (1993). "Fundamental algorithms for the star and pancake interconnection networks with applications to computational geometry". Networks. 23 (4): 215–225. CiteSeerX   10.1.1.363.4949 . doi:10.1002/net.3230230403.
  20. ↑ Bass, D.W.; Sudborough, I.H. (March 2003). "Pancake problems with restricted prefix reversals and some corresponding Cayley networks". Journal of Parallel and Distributed Computing. 63 (3): 327–336. CiteSeerX   10.1.1.27.7009 . doi:10.1016/S0743-7315(03)00033-9.
  21. ↑ Berthomé, P.; Ferreira, A.; Perennes, S. (December 1996). "Optimal information dissemination in star and pancake networks". IEEE Transactions on Parallel and Distributed Systems. 7 (12): 1292–1300. CiteSeerX   10.1.1.44.6681 . doi:10.1109/71.553290.
  22. ↑ Kumar, V.; Grama, A.; Gupta, A.; Karypis, G. (1994). Introduction to Parallel Computing: Design and Analysis of Algorithms. Benjamin/Cummings.
  23. ↑ Quinn, M.J. (1994). Parallel Computing: Theory and Practice (second ed.). McGraw-Hill.

Further reading

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.