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/14⁠n and ⁠18/11⁠n (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/16⁠n (approximately 1.06n) flips and an upper bound of ⁠(5n+5)/3⁠. The upper bound was improved, thirty years later, to ⁠18/11⁠n 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 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 [8] (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"). [9]

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

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

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

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 are equivalent. [16]

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: [17]

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

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). [17]

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:maxidx=max_index(arr,n)ifmaxidx!=n-1:ifmaxidx!=0:flip(arr,maxidx)flip(arr,n-1)n-=1arr=[15,8,9,1,78,30,69,4,10]pancake_sort(arr)print(arr)
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
1311213214511455613009610305057046318403095551849922756397834751525125357218305656614586536481868748522001

Sequences from The Online Encyclopedia of Integer Sequences:

Related Research Articles

<span class="mw-page-title-main">Discrete mathematics</span> Study of discrete mathematical structures

Discrete mathematics is the study of mathematical structures that can be considered "discrete" rather than "continuous". Objects studied in discrete mathematics include integers, graphs, and statements in logic. By contrast, discrete mathematics excludes topics in "continuous mathematics" such as real numbers, calculus or Euclidean geometry. Discrete objects can often be enumerated by integers; more formally, discrete mathematics has been characterized as the branch of mathematics dealing with countable sets. However, there is no exact definition of the term "discrete mathematics".

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

<span class="mw-page-title-main">Combinatorial optimization</span> Subfield of mathematical optimization

Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combinatorial optimization problems are the travelling salesman problem ("TSP"), the minimum spanning tree problem ("MST"), and the knapsack problem. In many such problems, such as the ones previously mentioned, exhaustive search is not tractable, and so specialized algorithms that quickly rule out large parts of the search space or approximation algorithms must be resorted to instead.

<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 a 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 graph theory, the metric dimension of a graph G is the minimum cardinality of a subset S of vertices such that all other vertices are uniquely determined by their distances to the vertices in S. Finding the metric dimension of a graph is an NP-hard problem; the decision version, determining whether the metric dimension is less than a given value, is NP-complete.

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">Crossing number (graph theory)</span> Fewest edge crossings in drawing of a graph

In graph theory, the crossing numbercr(G) of a graph G is the lowest number of edge crossings of a plane drawing of the graph G. For instance, a graph is planar if and only if its crossing number is zero. Determining the crossing number continues to be of great importance in graph drawing, as user studies have shown that drawing graphs with few crossings makes it easier for people to understand the drawing.

<span class="mw-page-title-main">Hypohamiltonian graph</span> Type of graph in graph theory

In the mathematical field of graph theory, a graph G is said to be hypohamiltonian if G itself does not have a Hamiltonian cycle but every graph formed by removing a single vertex from G is Hamiltonian.

In graph theory and theoretical computer science, the longest path problem is the problem of finding a simple path of maximum length in a given graph. A path is called simple if it does not have any repeated vertices; the length of a path may either be measured by its number of edges, or by the sum of the weights of its edges. In contrast to the shortest path problem, which can be solved in polynomial time in graphs without negative-weight cycles, the longest path problem is NP-hard and the decision version of the problem, which asks whether a path exists of at least some given length, is NP-complete. This means that the decision problem cannot be solved in polynomial time for arbitrary graphs unless P = NP. Stronger hardness results are also known showing that it is difficult to approximate. However, it has a linear time solution for directed acyclic graphs, which has important applications in finding the critical path in scheduling problems.

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 (classical) permutation pattern is a sub-permutation of a longer permutation. Any permutation may be written in one-line notation as a sequence of entries representing the result of applying the permutation to the sequence 123...; for instance the 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 entries of π has the same relative order as all of the entries of σ.

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.

Anna Lubiw is a computer scientist known for her work in computational geometry and graph theory. She is currently a professor at the University of Waterloo.

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

<span class="mw-page-title-main">Topswops</span> Mathematical problems devised by John Conway

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.

<span class="mw-page-title-main">Polygonalization</span> Polygon through a set of points

In computational geometry, a polygonalization of a finite set of points in the Euclidean plane is a simple polygon with the given points as its vertices. A polygonalization may also be called a polygonization, simple polygonalization, Hamiltonian polygon, non-crossing Hamiltonian cycle, or crossing-free straight-edge spanning cycle.

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. ↑ Chitturi, Bhadrachalam (2011). "A Note on Complexity of Genetic Mutations". Discrete Mathematics, Algorithms and Applications. 03 (3): 269–286. doi:10.1142/S1793830911001206.
  9. ↑ Dweighter, Harry (1975), "Elementary Problem E2569", Amer. Math. Monthly, 82 (10): 1009–1010, doi:10.2307/2318260, JSTOR   2318260
  10. ↑ 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..
  11. ↑ 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..
  12. ↑ 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 .
  13. ↑ 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.
  14. ↑ Berman, P.; Karpinski, M. (1999). "On Some Tighter Inapproximability Results". Proc. 26th ICALP (1999). Lecture Notes in Computer Science. 1644: 200–09.
  15. ↑ 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.
  16. ↑ Asai, Shogo; Kounoike, Yuusuke; Shinano, Yuji; Kaneko, Keiichi (2006). "Computing the diameter of 17-pancake graph using a PC cluster". In Nagel, Wolfgang E.; Walter, Wolfgang V.; Lehner, Wolfgang (eds.). Euro-Par 2006, Parallel Processing, 12th International Euro-Par Conference, Dresden, Germany, August 28 – September 1, 2006, Proceedings. Lecture Notes in Computer Science. Vol. 4128. Springer. pp. 1114–1124. doi:10.1007/11823285_117. ISBN   978-3-540-37783-2.
  17. 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.
  18. ↑ 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.
  19. ↑ 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.
  20. ↑ 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.
  21. ↑ Kumar, V.; Grama, A.; Gupta, A.; Karypis, G. (1994). Introduction to Parallel Computing: Design and Analysis of Algorithms. Benjamin/Cummings.
  22. ↑ 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.