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

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

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