The pancake sequence is also discussed at Sloane's Integer Sequences.

--------------------------------------------------------------------------

Darn! Looks like I took too long to get around to writing a
pancake-flipping program; you've already posted some answers.
Still, I seem to have more numbers than you showed, so I'll
pass these along.

I wrote a brute-force solver, but I was able to run it out to
12 pancakes. (It took about 2 hours.) I just do a breadth-
first search. For each possible stack I remember whether I've
reached it yet. Then, given all stacks reachable in a minimum
of N flops from the starting position, I try all flops from
each of those, and note any newly reached stacks. I repeat
for increasing N until all orderings have been achieved. I was
able to do this using 2 bits per stack, so 12! stacks fit in
only 100 megabytes or so, which meant I could keep it all in
memory instead of having to stuff data onto disk, so it ran
reasonably fast.

The sequence, including the 1-pancake case, is:
0 1 3 4 5 7 8 9 10 11 13 14

It is interesting to look at the shape of the curve formed by
the number of different P-pancake stacks requiring N flops.
The numbers go up nearly exponentially at first, i.e. 1, (P-1),
(P-1)(P-2), (P-1)(P-2)(P-2) - 1, but then the rate of growth
drops off, and after the peak the numbers drop precipitously.
As P increases, this precipitous tail occasionally grows large
enough to require an extra flop.

Here are the numbers for up to 12 pancakes, including sample
stacks requiring the maximum flops for 11 and 12.

-- Don Woods

==> p7 <==
1 stacks need 0 flops
6 stacks need 1 flops
30 stacks need 2 flops
149 stacks need 3 flops
543 stacks need 4 flops
1357 stacks need 5 flops
1903 stacks need 6 flops
1016 stacks need 7 flops
35 stacks need 8 flops

==> p8 <==
1 stacks need 0 flops
7 stacks need 1 flops
42 stacks need 2 flops
251 stacks need 3 flops
1191 stacks need 4 flops
4281 stacks need 5 flops
10561 stacks need 6 flops
15011 stacks need 7 flops
8520 stacks need 8 flops
455 stacks need 9 flops

==> p9 <==
1 stacks need 0 flops
8 stacks need 1 flops
56 stacks need 2 flops
391 stacks need 3 flops
2278 stacks need 4 flops
10666 stacks need 5 flops
38015 stacks need 6 flops
93585 stacks need 7 flops
132697 stacks need 8 flops
79379 stacks need 9 flops
5804 stacks need 10 flops

==> p10 <==
1 stacks need 0 flops
9 stacks need 1 flops
72 stacks need 2 flops
575 stacks need 3 flops
3963 stacks need 4 flops
22825 stacks need 5 flops
106461 stacks need 6 flops
377863 stacks need 7 flops
919365 stacks need 8 flops
1309756 stacks need 9 flops
814678 stacks need 10 flops
73232 stacks need 11 flops

==> p11 <==
1 stacks need 0 flops
10 stacks need 1 flops
90 stacks need 2 flops
809 stacks need 3 flops
6429 stacks need 4 flops
43891 stacks need 5 flops
252737 stacks need 6 flops
1174766 stacks need 7 flops
4126515 stacks need 8 flops
9981073 stacks need 9 flops
14250471 stacks need 10 flops
9123648 stacks need 11 flops
956354 stacks need 12 flops
6 stacks need 13 flops

Sample needing 13 flops: 10 6 3 8 5 2 7 4 9 1 11

==> p12 <==
1 stacks need 0 flops
11 stacks need 1 flops
110 stacks need 2 flops
1099 stacks need 3 flops
9883 stacks need 4 flops
77937 stacks need 5 flops
533397 stacks need 6 flops
3064788 stacks need 7 flops
14141929 stacks need 8 flops
49337252 stacks need 9 flops
118420043 stacks need 10 flops
169332213 stacks need 11 flops
111050066 stacks need 12 flops
13032704 stacks need 13 flops
167 stacks need 14 flops

Sample needing 14 flops: 11 6 8 10 5 2 7 3 9 4 1 12
------------------------------------------------------------------------

Better (10,6,3,8,5,2,7,4,9,1,11) problem solution is (8,3,9,4,8,6,10,5,7,5,3) -
11 flops!
It seems that "Sample needing 14 flops: 11 6 8 10 5 2 7 3 9 4 1 12"
could also be sorted with less flops, because the biggest element there is
already on the bottom..

Best wishes
Lauri Oherd
------------------------------------------------------------------------

Below is an analysis of how many flips are required for different sized
pancake stacks.

For length 3, there are 1 stacks requiring 0 flips
For length 3, there are 2 stacks requiring 1 flips
For length 3, there are 2 stacks requiring 2 flips
For length 3, there are 1 stacks requiring 3 flips

For length 4, there are 1 stacks requiring 0 flips
For length 4, there are 3 stacks requiring 1 flips
For length 4, there are 6 stacks requiring 2 flips
For length 4, there are 11 stacks requiring 3 flips
For length 4, there are 3 stacks requiring 4 flips

For length 5, there are 1 stacks requiring 0 flips
For length 5, there are 4 stacks requiring 1 flips
For length 5, there are 12 stacks requiring 2 flips
For length 5, there are 35 stacks requiring 3 flips
For length 5, there are 48 stacks requiring 4 flips
For length 5, there are 20 stacks requiring 5 flips

For length 6, there are 1 stacks requiring 0 flips
For length 6, there are 5 stacks requiring 1 flips
For length 6, there are 20 stacks requiring 2 flips
For length 6, there are 79 stacks requiring 3 flips
For length 6, there are 199 stacks requiring 4 flips
For length 6, there are 281 stacks requiring 5 flips
For length 6, there are 133 stacks requiring 6 flips
For length 6, there are 2 stacks requiring 7 flips

For length 7, there are 1 stacks requiring 0 flips
For length 7, there are 6 stacks requiring 1 flips
For length 7, there are 30 stacks requiring 2 flips
For length 7, there are 149 stacks requiring 3 flips
For length 7, there are 543 stacks requiring 4 flips
For length 7, there are 1357 stacks requiring 5 flips
For length 7, there are 1903 stacks requiring 6 flips
For length 7, there are 1016 stacks requiring 7 flips
For length 7, there are 35 stacks requiring 8 flips

For length 8, there are 1 stacks requiring 0 flips
For length 8, there are 7 stacks requiring 1 flips
For length 8, there are 42 stacks requiring 2 flips
For length 8, there are 251 stacks requiring 3 flips
For length 8, there are 1191 stacks requiring 4 flips
For length 8, there are 4281 stacks requiring 5 flips
For length 8, there are 10561 stacks requiring 6 flips
For length 8, there are 15011 stacks requiring 7 flips
For length 8, there are 8520 stacks requiring 8 flips
For length 8, there are 455 stacks requiring 9 flips

Rod Bogart

-------------------------------------------------------------------

For seven pancakes, there are 35 worst cases, each taking 8 flips to solve.

(1 3 7 5 2 6 4) (1 4 7 3 6 2 5) (1 5 2 7 4 6 3)
(1 5 3 7 2 6 4) (1 5 3 7 4 2 6) (1 5 7 3 6 4 2)
(1 5 7 4 2 6 3) (1 6 3 5 2 7 4) (1 6 3 7 5 2 4)
(1 6 4 2 7 5 3) (1 6 4 7 3 5 2) (1 7 3 5 4 6 2)
(1 7 4 6 2 5 3) (1 7 4 6 3 5 2) (1 7 5 3 6 2 4)
(1 7 5 3 6 4 2) (2 6 4 7 1 5 3) (3 5 2 7 4 6 1)
(3 6 1 4 7 2 5) (3 6 2 5 7 1 4) (3 7 5 2 6 1 4)
(4 2 6 3 7 1 5) (4 6 3 7 1 5 2) (4 7 2 6 3 1 5)
(5 1 7 3 6 2 4) (5 2 4 7 1 6 3) (5 2 7 3 1 6 4)
(5 2 7 4 1 6 3) (5 7 3 1 6 2 4) (5 7 3 4 1 6 2)
(6 2 4 1 7 3 5) (6 3 1 7 4 2 5) (6 3 5 1 7 4 2)
(6 4 1 7 3 5 2) (7 3 1 5 2 6 4)

This was determined by 18 minutes of brute forcing.

If the worst case for n pancakes is x flips, then the worst case for n +
1 pancakes can be no greater than x + 2 flips.

Getting the n + 1 pancake to the bottom of the pile will require 0, 1 or
2 flips, after which you can sort the n remaining pancakes in at most x
flips.
-jkmclean
--------------------------------------------------------------------------------
The total number of combinations is not huge, so it's easy to analyze all
the possible stacks. Attached is the tiny program in Python that does the
trick.
It's easier to move backwards, starting from the end, i.e. from the final
(1,2,3,4,5,...,n) stack. First we create all the possible stacks one step
before, then 2 steps before, etc. If the stack has been analyzed already, we
ignore it (because we already have the better solution). The resulting
PancakeProblem.solution dictionary maps all the stacks to their
corresponding solutions.

The (5, 3, 6, 1, 4, 2) problem solution is (2, 3, 6, 2, 4, 3, 2).

For 7 pancakes, there are 35 worst case stacks with 8-flop solutions.

I also analyzed the 8 pancake problem and it has 56 worst case stacks
(9-flop each).

Just in case, I attached those worst case stacks here too.

Thank you,

Igor Krivokon

************************************

pancakes.py (a Python program)
def turn(stack, n) :
substack = list(stack[0:n])
substack.reverse()
return tuple(substack) + stack[n:]

class PancakeProblem:
solution = {}

def __init__(self, num_of_pancakes):
self.num = num_of_pancakes

def process(self,position) :
cur_solution = self.solution[position]
for n in range(2,len(position)+1) :
new_position = turn(position,n)
if self.solution.has_key(new_position) :
continue
new_solution = (n,) + cur_solution
self.solution[new_position] = new_solution
self.to_process.append(new_position)

def find_solution(self) :
self.goal = tuple(range(1,self.num+1))
self.solution = { self.goal : () }
self.to_process = [ self.goal ]
self.processed = {}

while self.to_process :
pos = self.to_process.pop(0)
if not self.processed.has_key(pos) :
self.process(pos)
self.processed[pos] = 1

def compare(self,pos1,pos2):
return len(self.solution[pos2]) - len(self.solution[pos1])

def print_all_positions(self) :
positions = self.solution.keys()
positions.sort(self.compare)

for pos in positions :
print pos, ' => ', self.solution[pos]


problem = PancakeProblem(6)
problem.find_solution()
print problem.solution[(5, 3, 6, 1, 4, 2)]

# problem.print_all_positions()

-------------------------------------------------------------------------
Hi, Ed; and happy new year!

I would submit some remarks about the pancake-sorting problem.

Concerning the 6-pancakes case (but the remark applies in general) the
knowledge of ALL the worst cases implies that the problem MUST have many
solutions (at least 5) because the first spatula-flop is free: in fact no
choice brings to one of the worst cases...
And in fact, dots denoting where the spatula will operate, we have:
53.6142 356.142 653142. 24.1356 4213.56 312.456 21.3456 123456
536.142 635142. 24.1536 4215.36 51243.6 34.2156 4321.56 123456
5361.42 16354.2 45.3612 543.612 3456.12 654312. 21.3456 123456
53614.2 416.352 614352. 2534.16 43.5216 345.216 54321.6 123456
536142. 24.1635 42163.5 3612.45 216.345 6.12345 54321.6 123456

On the other hand, I want to point out that the knowledge of all the worst
cases for 6 pancakes easely allow to simplify the brute-force approach for 7
pancakes.

CLAIM: any 7-pancakes pile can be sorted by at most 8 flops; and 8 flops are
needed for some pile.
PROOF:
(1) If the number 7 (say: the greatest pancake) is at the bottom, 7 flops
suffice: we simply work with the remaining 6-pancakes-pile. Remark that in
fact 6 flops suffice in all cases but two: 5361427 and 4625137 (the worst
cases in the 6-pancakes framework, followed by the 7)
(2) If the number 7 is on the top, we start by reverting the whole pile.
Thus 7 flops suffice in all cases but two: the cases 7241635 and 7315264
could require 8 flops. In fact the first one can be solved with 7 flops:
7241.635 14.27635 412763.5 367.2145 7632154. 45123.67 321.4567 1234567
while for the second one the best one can do (as my Computer told me) is
given by the 8 flops:
73.15264 371526.4 6251.734 15.26734 512.6734 21567.34 7651234. 4321.567
1234567
(3) In the remaining cases, let us firstly try the most obvious strategy of
choosing as first flop the one that brings the 7 on the top. It works with
only 5 exceptions, say:
3715264, 1375264, 5137264, 2513764, 6251374
where the result is the bad case of point (2); all remaining cases can thus
be solved by (at most) 8 flops.
(4) The 5 remaining cases require a different treatement, the naive strategy
requiring 9 flops. My Computer says that all but one require 7 flops; and
the case 1375264 requires 8 flops, e.g.:
13.75264 317526.4 625.7134 52.67134 2567.134 7652134. 4312.567 21.34567
1234567

Let me add a final remark. I often play a similar game with coins: I put
some coins on my hand, in such a way that (as shown in the enclosed picture
"spatula.jpg") it is easy to choose and revert an "upper block" of any
length. When trying to get the coins in decreasing order, a simplification
is given by the fact that some coins can have the same size; but, asking for
"all coins face-up", a more difficult problem arises.

Ciao, Claudio Baiocchi
------------------------------------------------------------------------
Interesting problem, pancake sorting. The link you included in your
discussion has the answer to your question of sorting {5,3,6,1,4,2) with
(2,3,6,2,4,3,2). There are many other answers such as (2,4,5,2,4,6,2),
(4,5,2,3,4,6,2) and (3,6,4,5,2,3,4).

Any stack of size n > 1 can be sorted with at most 2*n-3 flops with the
following algorithm:
1) m = n
2.1) Flop the stack so that the maximum element of the first m items is
on top.
2.2) Flop the first m items (placing the maximum at the bottom of the m
items).
2.3) m = m - 1
3) Repeat with steps 2.1 through 2.3 while m > 2
4) Flop the top 2 items if they are not already sorted.

A better algorithm might involve selecting flops that order the stack
into pairs, then into groups of 4, then groups of 8...

You can also take the approach analogous to a perfect quicksort.


- Ron Zeno
--------------------------------------------------------------------------
Pancake sorting problem.

It seems that there are 35 "worst" cases for the 7 pancakes problem,
which can be solved using 8 flops. One of them is {1,5,2,7,4,6,3}.

9 Flops are required for solving any of the 455 worst cases for 8
pancakes, e.g. {1,5,2,7,4,8,6,3}.

An interesting Pancake problem variant appears if you distinguish "top"
and "bottom" in each pancake. Besides sorting them from smallest to
largest, final position must present all pancakes with "top" in the
upper side. In this case, it seems that the number of flops required
equals 2N, N being the number of pancakes, for N= 3, 4, 5 or 6. Number
of "worst" cases appears to be respectively 2,3,4,1 for 3,4,5,6
pancakes. {1,2,3,4,5..} with the bottom in the upper side is always one
of these worst cases.

I have to check these results, but these regularities perhaps indicate
that there is a simple algorithm for an optimum solution.

Thank you for your excellent Web page.

Jesús Sanz

-------------------------------------------------------------------------
Ed,

I wrote an exhaustive search program for the Pancake Sorting Problem. For 7
pancakes, the maximum number of flops needed is 8. There are 35 worst case
stacks, of which the "first" and "last" are (1, 3, 7, 5, 2, 6, 4) and (7, 3,
1, 5, 2, 6, 4).

Regards,
Al Zimmermann
--------------------------------------------------------------------------
Hi Ed,
My father, Dick Saunders Jr. showed me your page, so I
came up with a solution for your pancake sorting
problem. The first sequence was 536142. I've used a
slash (/) to show you where I flipped the cakes.

1st stack: 53/6142
2nd: 356/142
3rd: 653142/
4th: 24/1356
5th: 4213/56
6th: 312/456
7th: 21/3456
final: 123456.

:) Have a good day. Thanks for the fun.
---------------------------------------------------------------------------
Hi Ed,
Happy New Year. May 2002 by a happy, peaceful and productive one for
you.

I'd flip the six pancakes thus, though I dare say there are other
possibilities:

536142
356142
653142
241356
421356
312456
213456
123456

Brute force can always restore a stack of n pancakes in 2n-3 flips by
getting the largest to the top, then to the bottom of the
as-yet-unsorted part. e.g.
536142
635142
241536
514236
324156
423156
132456
312456
213456
<2 already on top, so skip a step, otherwise skip last 2 steps>
123456

That's only two more than the optimal solution, so optimization isn't
buying much.

Best wishes
Chris Lusby Taylor
-----------------------------------------------------------------------------
The second worst case for 6 pancakes can be solved with 7 flops:
1. (1,6,3,5,4,2) or (3,5,6,1,4,2)
2. (4,5,3,6,1,2) (4,1,6,5,3,2)
3. (5,4,3,6,1,2) (5,6,1,4,3,2)
4. (3,4,5,6,1,2) (1,6,5,4,3,2)
5. (6,5,4,3,1,2) (2,3,4,5,6,1)
6. (2,1,3,4,5,6) (6,5,4,3,2,1)
7. (1,2,3,4,5,6) (1,2,3,4,5,6)
-- xdamof

----------------------------------------------------------------------------------------

Hi Ed,

I did an exhaustive search for stacks of 7 and 8 pancakes.
The maximum number of flips needed is 7 and 8 respectively. For both cases
there are tens of different 'configurations' that need the maximum.

It starts to look like the maximum number is always less than (N+1), with
the N the number of pancakes.
I wonder if this can be proven.

Greetings and best wishes for a happy and healthy 2002,

Luc Kumps