October 9, 2008

Improved Pancake Sorting

You have a stack of pancakes, each one a different size. You want to rearrange the pancakes in order of size, with the smallest one on top and the largest on the bottom. But your only option is to insert a spatula at some point in the stack and flip the upper pancakes into reverse order. What's the maximum number of such flips that you'll ever need to sort the pancakes?

This classic mathematical problem, often described as pancake sorting or more formally as prefix reversal, has been around since 1975. Now, a team of computer science students has made the first improvement in nearly 30 years in one theoretical limit on solving the problem.

The maximum number of flips ever needed to rearrange a stack of n pancakes is known as the nth pancake number, Pn. For five pancakes, for example, no more than five flips are ever needed, so P5 = 5.

Until recently, pancake numbers were known only up to n = 13.


In the last few years, teams of Japanese computer scientists have used clusters of computers to work out values for n = 14 to 17: "Computing the diameter of 17-pancake graph using a PC cluster."


Early on, researchers established theoretical bounds on pancake numbers. Initial work established that Pn had to be at least n and no more than 2n – 3, for n greater than 2.

In 1979, William H. Gates and Christos H. Papadimitriou improved on the upper and lower limits, showing that (5n + 5)/3 flips always suffice and that 17n/16 flips may be needed. Bill Gates, co-founder of Microsoft, had worked on the problem when he was a sophomore at Harvard, as described in a recent NPR story, and published the resulting paper, his only technical contribution to the mathematical literature, in collaboration with Papadimitriou, then a young professor at Harvard and now at the University of California, Berkeley. The paper, published in Discrete Mathematics, was titled "Bounds for sorting by prefix reversal."

In 1997, Mohammad H. Heydari and I. Hal Sudborough improved the lower bound to 15n/14.

In 2008, students at the University of Texas at Dallas, working with Sudborough, used a lot of computation to establish an improved upper bound, (18/11)n. A paper describing the results, "An (18/11)n upper bound for sorting prefix reversals," was published in Theoretical Computer Science (Vol. 410, no. 36, August 31, 2009, pp. 3372-3390). The authors are B. Chitturi, Bill Fahle, Zhaobing Meng, Linda Morales, Charles Shields, Hal Sudborough, and Walter Voit.

The effort took about two years. "Improving the upper bound for the pancake problem has challenged mathematicians and computer scientists for 30 years," Sudborough noted. "We succeeded through the dedicated efforts of our team, the willingness of all to devote many hours to analysis, verification, and innovation, and our overriding belief that a better bound could be discovered."

4 comments:

Anonymous said...

I greatly enjoyed your recent MAA Online article on "Pancake sorting" and was pleasantly surprised to recognize the nice "pancake" metaphor as the basis of an early computer game we named "Reverse" that was created popularized at "People's Computer Company" and published back in May 1973!

See http://www.svipx.com/pcc/gameslist.html

I don't have access to the old newsletter right now, so don't know if we mentioned it, but I'm sure we were aware of the easy N and 2N-3 bounds at the time, and the fact that sharper general bounds might be "glitchy" based on our observations for small N.

I have often idly wondered about what we called the "diameter of the Reverse move graph" over the years, but was unaware until your article that anybody else had ever been interested in it, nor that Bill Gates had worked on it!

Thanks for the fascinating update!

Anonymous said...

We ran a programming contest on this problem in 2004:
http://recmath.org/contest/Pancakes/index.php

At this occasion, we computed the pancakes up to N=14:
http://tomas.rokicki.com/pancake/

And I posted a message after having finished N=15, with a cluster of 10 computers:
http://tech.groups.yahoo.com/group/AlZimmermannsProgrammingContests/message/1275
http://tech.groups.yahoo.com/group/AlZimmermannsProgrammingContests/message/1276

The solutions for N=15 are here:
http://euler.free.fr/pancakes/Sol15.zip

I never completed N=16, because of boredom (and my cluster was colleagues' computers, and they needed their computers).

BTW, Tomas listed all the hardest pancakes known here:
http://tomas.rokicki.com/pancake/witnesses.html

JC

Anonymous said...

So how is (18/11)n an improvement over (15/14)n for an Upper bound? 18/11 is greater than 15/14, last I checked.

Unknown said...

Dear,
18/11 is an improvement over 5/3 for UPPER bound.
15/14 is a lower bound which is an improvement over 17/16 as proposed by Gates et. al.

Upper bounds with smaller values and lower bounds with higher values are what we seek.

Regards.
___________________________________
Anonymous said...
So how is (18/11)n an improvement over (15/14)n for an Upper bound? 18/11 is greater than 15/14, last I checked.

11:34 AM