Pancakes, Graphs and the Genome of Plants (5/10/2001)

Joseph Malkevitch
Mathematics and Computing Department
York College (CUNY)
Jamaica, New York 11451

email:

malkevitch@york.cuny.edu

web page:

http://york.cuny.edu/~malk

Introduction

In 1975, Jacob Eli Goodman posed the following problem in the American Mathematical Monthly under the pseudonym of Harry Deweighter (harried waiter):

The chef in our place is sloppy, and when he prepares a stack of pancakes they come out all different sizes. Therefore, when I deliver them to a customer, on the way to the table I rearrange them (so that the smallest winds up on top, and so on, down to the largest on the bottom) by grabbing several from the top and flipping them over, repeating this (varying the number I flip) as many times as necessary. If there are n pancakes, what is the maximum number of flips (as a function of n) that I shall ever have to use to rearrange them?

What is exciting about this problem is that not only is it a problem in pure mathematics of great charm, but also it has led to a variety of ideas of great applicability. Furthermore, the original problem Goodman posed is not completely resolved despite the simplicity in stating the problem.

The purpose of this note is to survey some of what is known about the pancake flipping problem, to suggest some projects that might make interesting work for high school students and undergraduates, and to show how questions such as this are valuable ones to show students in a wide variety of classroom settings. The problem connects with many important and fundamental ideas in computer science and mathematics and affords an illustration of how these ideas can be looked at in an attractive context.

Notation, Background and Extensions

It will be convenient to introduce some notation and terminology in order to discuss this problem. Let us suppose that we have n (circular) pancakes, each of a different diameter. The pancakes are numbered from 1 to n with 1 being the pancake of smallest diameter and n being the pancake with largest diameter. We imagine being given one of the possible n! stacks of the n pancakes sitting on a plate. The name given to a particular stack of pancakes will be a string of the numbers 1 to n where we think of the leftmost number in the string corresponding to the top pancake in the stack and the rightmost number in the string as being the pancake sitting on the plate. A place where a spatula is inserted into the string will be referred to as a break.

Originally, Goodman considered one way (called here left flipping) of taking a stack of pancakes and transforming it to another stack using a single spatula to perform the flip. However, we will consider a broader collection of operations that can be done on the string corresponding to the collection of pancakes:

Left Flipping: Reverse the section of the string to the left of the break.

A more common name for left flipping is prefix reversal.

Symmetric flipping: Reverse the section of the string to the left and right of the break.

Right flipping: Reverse the section of the string to the right of the break.

Section flipping: Reverse the section of the string between two breaks (between two spatulas).

A more common name for section flipping is a reversal.

Another consideration in section flipping is to only allow section flips of the same size, that is, one is only allowed to flip consecutive elements of a fixed length. Additionally, one might allow section flips of some, but not all possible lengths (e.g. length 2 or n ; length 2 or length 3).

Outside section flipping: Reverse both sections outside the part between the two breaks.

For each of these types of operations we can consider the following problems:

a. Using the given operation is it possible to take any stack of pancakes and sort it, that is, restore it to the order 1,...,n?

b. If it is possible to use the operation to sort, what is the minimum number of the operations that is sufficient to guarantee that the pancake stack can be sorted in this number of operations, regardless of what particular stack one starts with?

c. For each n is there some stack of pancakes which requires at least a certain number of flips to sort?

d. Is there some fraction of the pancakes which require at least a certain number of operations to restore to sorted order?

e. On the average how many operations are needed to sort a pancake stack?

These problems are typical of a variety of questions of a similar spirit that are of general interest to mathematicians and computer scientists in a wide variety of contexts.

In order to get additional insight into pancake problems it is helpful to use an associated graph. Given the n! strings on the numbers 1 to n, we can construct a graph in the following way. Represent each of the n! strings by a vertex of the graph. Join two vertices by an edge if, using an operation of the kind above, one can transform one of the strings into the other. Thus, for each type of flip one gets a different graph, though one can think of the graphs as subgraphs of some others in some cases, and one might get isomorphic graphs for operations which are described differently. The problem of sorting any pancake stack into size order has an interpretation in the graph theory context. For any vertex in the graph is it possible to find a path from that vertex to the vertex which represents the sorted stack? If the graph created is connected, then sorting is possible using the particular operation used to create that graph. Otherwise, one gets components which represent pancake stacks that are mutually reachable.

To illustrate the idea, Figure 1 gives a few examples. Rather than draw the full graph for various operations that we might consider, I will show the effect of the flips on a single vertex of the graph, namely, 1234. Figure 1 (a) shows the result of prefix reversal, while Figure 1 (b) shows the result of reversing what is to the left and right of the break. By symmetry all the other vertices will have the same structure; however, it is not clear how to create nice drawings of these graphs even for n = 4, and certainly not for general values of n. Also note that the graphs produced by these two operations can not be isomorphic, because they will have different valences though they are defined for the same set of vertices.

Figure 2 shows the full left-flip graph for n = 3.

High School or Undergraduate Research Projects

A variety of questions can be posed about each of these graphs:

0. Is there a nice way of constructing the graph based on n+1 pancakes from the graph based on n pancakes?

Note: There is a simple way of constructing the (d+1)-cube from d-cubes.

1. Is the graph in each family hamiltonian?

2. What is the vertex connectivity of the graphs in each family?

3. What is the edge connectivity of the graphs in each family?

4. What is the chromatic number of the graphs in each family?

5. What is the chromatic index of the graphs in each family?

6. What is the automorphism group of the graphs in each family?

7. What are the crossing number and rectilinear crossing number of the graphs in each family?

8. What is the thickness of the graphs in each family?

9. What is the genus of the graphs in each family?

10. Do the graphs in each family have a spanning tree with no vertices of valence two?

11. Obtain nice drawings of the small pancake graphs. ( Nice drawings are often useful in getting insight into the properties of combinatorial objects.)

Up until now we have looked at the graph associated with flips for a pancake stack of size n. It turns out that it is also useful to look at graphs associated with a particular pancake stack and the internal structure of the sizes of the pancakes within that stack.

To see what might be done consider the following particular example of a stack of 8 pancakes: 1, 3, 4, 8, 5, 7, 6, 2. As you can see, some clusters of the pancakes are already in size order or reverse size order. Perhaps we can use information of this kind to help find the optimal sorting sequence for this particular pancake stack. With this in mind we will define the breakpoint graph of a permutation p. Up to now we have not used the word permutation but, in fact, a stack of n pancakes, as we have coded them, is nothing more than a permutation of the numbers 1 to n. For technical reasons, it is convenient to define the breakpoint graph of a permutation 0, 1, ..., n, n+1. We join the vertices named i and i+1 by a thick edge and we join vertices i and j by a thin edge if |i-j| = 1, that is, if these two vertices are adjacent (in the left to right representation of the permutation). Note that this means that some vertices can be joined by both thick and thin edges, so the graph involved can have digons. The structure of this (labeled) graph, which is even-valent, helps make it possible to get some useful information about the sorting process. As an example of these ideas, starting with the pancake stack 1, 3, 4, 8, 5, 7, 6, 2, we construct the associated permutation 0, 1, 3, 4, 8, 5, 7, 6, 2, 9. The breakpoint graph of this permutation is given in Figure 3.

A rather nice and useful extension of the pancake problem was suggested by W. Gates (yes, the Bill Gates) and C. Papadimitriou [12]. It is in the spirit of what is done in mathematical modeling. One might choose to model pancakes as we have done, but in the real world sometimes a pancake gets burned. In the worst case every pancake might have a good side and a burned side. Thus, one might not only want to sort the pancakes by size but make sure the good side of each pancake is towards the top. The burned pancake problem assumes that each pancake has a good side and a burned side and asks for the minimum number of left flips that transform any stack of pancakes into a sorted-by-size stack where each pancake has its good side towards the top. It is convenient again to number the pancakes 1 to n from smallest to largest and use a negative sign when the pancake has its burned side up. Thus, the sorted stack of pancakes is 1, 2, ..., n and the stack that is in the correct size order but for which each pancake has its burned side up is -1, -2, ..., -n, usually denoted -In. Sorting burned pancakes also can be used to sort pancakes that are not burned. A rather nice observation is mentioned in Heydari and Sudborough [16]. Let us refer to two pancakes which are consecutive in size as an adjacency. If once two pancakes become adjacent we agree never to separate them, then we can think of the adjacent pair as a burnt pancake. When the adjacent pair has the smaller of the two on top, it will be thought of as a burnt pancake with its good side up and when the adjacent pair has the smaller of the two down, then it will be thought of as a burned pancake with its burnt side down. When sorting pancakes, we can view the stack as shrinking as the sorting creates adjacencies until the point where the entire stack becomes transformed into a single burned pancake in the end. One can construct breakpoint graphs associated with burned pancake stacks in a manner similar to the one used for unburned pancakes.

To test your intuition, as a function of n, what do you think is the number of flips necessary to restore any stack of pancakes (burned pancakes) to sorted order?

For pancakes (not the burned case) it is very easy to see that one does not need more than 2n flips. Suppose one wants to move a particular pancake j to the ith position in the stack. Put the spatula after the jth pancake and flip. This moves the jth pancake to the top of the stack. Now put the spatula after position i and flip. This moves the top pancake, the one numbered j, to the ith position. We can move the biggest pancake to position n, the next biggest to position n-1, etc., each step being carried out in no more than 2 flips. By the time we put the second smallest pancake in its position, the first pancake is already in place, so, in fact, we have shown that we need at most 2n - 2 flips for any n.

What is Known?

An excellent survey of the history of the pancake problem can be found in Heydari and Sudborough [16]. Here a few summary observations will be made:

1. Gates and Papadimitriou showed that for a particular pancake stack π, if f(π) denotes the maximium number of left flips to sort π, then (17/16)n ≤ f(n) ≤ 5(n+1)/3 where f(n) denotes the maximum number of left flips required to sort any stack of n pancakes. Exact computations of f(n) for n ≤ 13 have been obtained.

2. If we use g(n) to denote the maximum number of left flips to restore a stack of burned pancakes to sorted order, then g(n) has been computed exactly for n ≤ 11. Cohen and Blum [9] conjecture that the stack -In is the hardest stack of burned pancakes to sort. They conjecture that any n burned pancakes can be sorted with at most 3(n+1)/2 left flips. If it turns out the -In is the hardest stack to sort, then it will mean that the left flip graphs based on either burned or unburned pancakes would have diameter no more than 3(n+1)/2.

Applications to Computer Architecture

On first hearing it may seem as if the pancake problem and some of the extended types of flips raised here have little to recommend their solution other than intellectual curiosity. However, it turns out, as is often the case with development of ideas in pure mathematics, that one can apply these ideas.
One set of applications comes about in the area of computer science. Until relatively recently, the basic design for a practical computer consisted of a single elaborate processor. However, in more recent times with the lower cost of manufacturing chips of different kinds, it has become possible to take relatively powerful chips, each a separate computer, and hook them up together into a parallel architecture computer. The idea is that for certain kinds of problems, which can be broken down into parts which can be worked on separately, one can solve the problem faster by using a parallel computer than the usual serial kind. This is true even though the parallel processors are nowhere near as powerful as one would need to solve the same problem in the same amount of time on a serial computer. In order to work together, these small computers (usually referred to as processors) must be connected so that at certain times they can exchange or transmit information to other processors. In some parallel machine architectures there are issues concerning which processors can or can not share some piece of common memory. There are various geometries or topologies that can be used for connecting up the processors.

The simplest of these architectures is that of a ring or a cycle. More complicated is the hypercube architecture, but an alternative choice to the hypercube architecture is the pancake topology. Using connections between processors that mimic the way flips of pancakes are related to each other one can create an architecture. The most common operation used in this case is the one I have called section flipping; the resulting computer networks are said to have the pancake topology. It turns out that the degrees of the vertices of the pancake network are n-1 (i.e. there are n-1 connections from each processor to other processors). The diameter of a graph is the minimum number of edges in a path between any pair of vertices of the graph. This number is relatively low for pancake graphs in light of the large number of vertices that they have. This is very desirable in terms of the architecture of a computer network.

Applications to Molecular Biology

Another rather unexpected application of this circle of ideas has also emerged in molecular biology. Recent major breakthroughs in understanding genetics came from the Crick-Watson model of DNA and the discovery of a triplet code that shows how the linear sequences of A, C, G, and T in DNA code the twenty different amino acids. In June, 2000 a preliminary draft of the human genome was announced based on the DNA sequencing. Different humans have very slightly different genomes and similar species have rather similar genomes. One mechanism for the reason why these genomes are different are the accumulated differences built up in the genetic material of different species due to random mutation and random mating. However, in the 1980's it was discovered that there was another mechanism of evolution that had not been explicitly noted before. It was discovered that in some plants gene sequences were the same but different in order, in the same way that a, a, b, c has the same letters as c, a, a, b but in a different order. This suggested that it might be of value to look at mechanisms by which gene orders might get shuffled. One way of doing this is exactly the idea of pancake transformations. In particular, the computer scientists and the biologists they were working with developed ideas concerning transforming one permutation into another permutation of the same letters using reversals. This idea is identical with the concept of section flipping defined above, except that in the biology literature it is called a reversal, and the problem of sorting using reversals is called the reversal distance problem. There is already a large literature on mathematical questions related to these ideas. A pioneer in the development of these ideas and methods has been Pavel Pevzner, and in his recent book Pevzner [17] he treats many aspects of the combinatorial problems associated with sorting permutations.

References:

1. Akers, S. and B. Krishnamurhty, A group-theoretic model for symmetric interconnection networks, IEEE Trans. Computers 38 (1989) 555-566.

2. Akl, S.G., and K. Qiu, I. Stojmenovic, Computational geometry on the star and pancake networks, Proceedings of the Third Canadian Conference on Computational Geometry, Vancouver, British Columbia, August, 1991, pp. 252 - 255.

3. Akl, S.G. and K. Qiu, I. Stojmenovic, Data communication and computational geometry on the star and pancake interconnection networks, Proceedings of the Third IEEE Symposium on Parallel and Distributed Processing, Dallas, Texas, December 1991, pp. 415 - 422.

4. Bafna, V. and P. Pevzner, Sorting by transpositions, In Proc. 6th Annual ACM-SIAM Symposium on Discrete Algorithms, 1995, pp. 614-623.

5. Caprara, A., Sorting by reversals is difficult, In S. Istrail, P. Pevzner, and M. Waterman, (eds.), Proceedings of the First Annual International Conference on Molecular Biology (RECOMB-97), ACM Press, New York, 1997, pp. 75-83.

6. Caprara, A., Formulations and hardness of multiple sorting by reversals, in Proc. of 3rd. Conference on Computational Molecular Biology (RECOMB 99), ACM Press, New York, 1999, pp. 84-93.

7. Chaudhuri, S. and T. Hagerup, Prefix Graphs and Their Applications, Saarbruecken, 1994.

8. Chen, T. and S. Skiena, Sorting with fixed-length reversals, Discrete Applied Math., 71 (1996) 269-296.

9. Cohen, D. and M. Blum, On the problem of sorting burnt pancakes, Discrete Applied Mathematics 61 (1995) 105-120.

10. Deweighter, H. (pseudonym for Jacob Eli Goodman), American Mathematical Monthly 82 (1975) 1010.

11. Garey, M. and D. Johnson, S. Lin, American Mathematical Monthly 84 (1977) 296.

12. Gates, W. and C. Papadimitriou, Bounds for sorting by prefix reversal, Discrete Math. 27 (1979) 47-57.

13. Goodman, J., Personal communication, 2000.

14. Gyori, E. and E. Turan, Stacks of pancakes, Studia Sci. Math. Hungar. 13 (1978) 133-137.

15. Hannenhalli, S. and P. Pevzner, Towards a computational theory of genome rearrangements, in Computer Science Today, J. van Leeuwen (ed.), Lecture Notes in Computer Science, Volume 1000, Springer-Verlag, 1995, pp. 184-202.

16. Heydrari, M. and H. Sudborough, On the diameter of the pancake network, Journal of Algorithms 25 (1997) 67-94.

17. Pevzner, P., Computational Molecular Biology, MIT Press, Cambridge, 2001.

18. Qiu, K. and H. Meijer, A. Akl, Parallel routing and sorting on the pancake network, in Proceedings of the Third International Conference on Computing and Information, Lecture Notes in Computer Science, Volume 497, Springer-Verlag, New York, 1991, pp. 360-371.

19. Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica, Addison-Wesley, Reading, 1990.