cp's OEIS Frontend

"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 at 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 a(n) of n) that I will ever have to use to rearrange them?" [Dweighter]

J. K. McLean (jkmclean(AT)webone.com.au): 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.

Comments based on email message from Brian Hayes, Oct 10 2007: (Start)

We are interested in the diameter of the graph where the vertices are all possible permutations of n elements and an edge connects p(i) and p(j) if some allowed reversal transforms p(i) into p(j).

There are at least two dimensions to consider in describing the various sorting-by-reversal problems: (a) Are the elements of the sequence signed or unsigned? and (b) Are we constrained to work only from one end of the sequence?

The standard pancake problem has unsigned elements and allows moves only from the top of the stack; the diameter is given by the present sequence.

The "burnt-pancake" problem has signed elements and allows moves only from the top of the stack. This is sequence A078941 (and also A078942).

The biologically-inspired sorting problems I was writing about in the Amer. Scientist 2007 column dispense with the one-end-only constraint. You're allowed to reverse any segment of contiguous elements, anywhere in the permutation. For the unsigned case, a(n) = n-1 (cf. Kececioglu and Sankoff).

Finally there is the signed case without the one-end constraint. This was the main subject of my column and corresponds to sequence A131209. (End)

Brian Goodwin (brian_goodwin(AT)yahoo.com), Aug 22 2005, comments that the terms so far match the beginning of the following triangle:

0

1

3 4 5

7 8 9 10 11

13 14 15 16 17 18 19

21 22 23 24 25 26 27 28 29

31 32 ...

Is this a coincidence? Answer from Mikola Lysenko (mclysenk(AT)mtu.edu), Dec 09 2006: Unfortunately, Yes! That triangular sequence has the closed form: a(n) = n - 1 + floor(sqrt(n-2)). However, Gates and Papadimitrou establish a lower bound on the pancake sequence of at least (17/16)*n. For sufficiently large n, this is always larger than the number in the triangle.

Marc Lebrun writes that in 1975 he was involved with a group called the "People's Computer Company" and among the many early computer games they created and popularized was one called "Reverse", which they published in their newspaper. See link.

M. Peczarski and I affirm the value a(19) = 22 as given by Simon Singh. Firstly, a(19) >= 22 as stated in the paper by Heydari Sudborough. This statement is mentioned on page 93. There two permutations of order 19 are given which need at least 22 flips. These permutations are 1,7,5,3,6,4,2,8,14,12,10,13,11,9,15,17,19,16,18 and 1,7,5,3,6,4,2,8,14,12,10,13,11,9,15,18,16,19,17. Making use of a branch-and-bound algorithm, we can confirm that their statement is correct. Together with the result that a(18) = 20, this gives a(19) = 22. Both values a(18) = 20 and a(19) = 22 were also proved in the paper by Cibulka. - Gerold Jäger, Oct 29 2020

In a 'spatula flip', a spatula is inserted below any pancake and all pancakes above the spatula are lifted and replaced in reverse order.

It is conjectured that this initial configuration is a worst case for the general problem of sorting burnt pancakes. If so, then this sequence is identical to A078941.

See also the comments in A058986 for background information.

From Glenn Tesler: (Start)

Let d_max = a(n) be the maximal distance.

Then d_max = n for n=0,1,3; d_max = n+1 except for n=0,1,3; however, there are many permutations achieving the max, not just the 2 Gollan permutations as in the unsigned case.

The formula for reversal distance is d = n + 1 - c + h + f,

where c is the number of cycles in the breakpoint graph, h is the number of "hurdles" and f is the number of "fortresses" (0 or 1).

It turns out that c >= h+f.

This is because each hurdle is composed of one or more cycles, distinct from those in other hurdles, and fortresses can be worked into that, too.

So we may rewrite distance as d = n+1 - (c-h-f), where c-h-f>=0. Thus d_max <= n+1.

Except for n=0,1,3, it turns out we can make c-h-f=0.

When n=0: d(null,null) = 0, so d_max = 0 (has c=1, h=0)

When n=1: d( 1, -1 ) = 1, d( 1, 1 ) = 0, so d_max = 1 (first one has c=1, h=0)

When n=2: d( 2 1, 1 2 ) = 3, all other d(sigma, 1 2) < 3 (has c=h=1)

When n=3: d_max = 3 (25 solutions, found by brute force; 20 with c=1, h=0; 5 with c=2, h=1)

When n>3: d_max = n+1 and there are many solutions, obtained by creating a situation in which c=h, f=0. One of them is

n=2m: n 1 m+1 2 m+2 3 m+3 ... m-1 2m-1 m (has c=h=1)

n=2m+1: n 1 m+1 2 m+2 3 m+3 ... m 2m (has c=h=2)

Note that these are indeed signed permutations, in which all signs happen to be positive. This is because "hurdles" require all the signs to be the same.

Also note that these are just examples to show that at least one permutation has d=n+1, which proves d_max=n+1 by the bound; however, there are many more signed permutations that also achieve d=n+1. (End)