login
This site is supported by donations to The OEIS Foundation.

 

Logo

Many excellent designs for a new banner were submitted. We will use the best of them in rotation.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A058986 Sorting by prefix reversal (or "flipping pancakes"). You can only reverse segments that include the initial term of the current permutation; a(n) is the number of reversals that are needed to transform an arbitrary permutation of n letters to the identity permutation. 6
0, 1, 3, 4, 5, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 19 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

"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 17n / 16. For sufficiently large n, this is always larger than the triangle.

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

REFERENCES

Shogo Asai, Yuusuke Kounoike, Yuji Shinano and Keiichi Kaneko, Computing the Diameter of 17-Pancake Graph Using a PC Cluster, Proc. Euro-Par 2006, LNCS 4128, pp. 1114-1124, 2006 Springer Verlag

Bafna, Vineet and Pavel Pevzner. 1996. Genome rearrangements and sorting by reversals. SIAM Journal on Computing 25:272-289.

Bergeron, Anne. 2005. A very elementary presentation of the Hannenhalli-Pevzner theory. Discrete Applied Mathematics 146:134-145.

Bergeron, Anne and Francois Strasbourg. 2001. Experiments in computing sequences of reversals. Proceedings of the First International Workshop on Algorithms in Bioinformatics, pp. 164-174. Berlin: Springer-Verlag.

Caprara, Alberto. 1997. Sorting by reversals is difficult. Proceedings of RECOMB '97: The First International Conference on Computational Molecular Biology, pp. 75-83. New York: ACM Press.

J. J. Chew, III (jjchew(AT)math.utoronto.ca), personal communication, Jan 15 and Feb 08, 2001, computed a(10) - a(13).

B. Chitturi, W. Fahle, Z. Meng, L. Morales, C. O. Shields, I. H. Sudborough and W. Voit, An (18/11)n upper bound for sorting by prefix reversals, Theoret. Comput. Sci. 410 (2009), no. 36, 3372-3390.

Harry Dweighter ["Harried Waiter", pseudonym of Jacob E Goodman], Problem E2569, Amer. Math. Monthly, 82 (1975), 1010. Comments by M. R. Garey, D. S. Johnson and S. Lin, loc. cit. 84 (1977), 296.

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

E. Gy\"{o}ri and G. Tur\'{a}n, Stack of pancakes, Studia Sci. Math. Hungar., 13 (1978), 133-137.

Hannenhalli, Sridhar and Pavel A. Pevzner. 1999. Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals. Journal of the ACM 48:1-27.

Brian Hayes, Sorting out the genome, Amer. Scientist, 95 (2007), 386-391.

Kececioglu, J. D. and D. Sankoff. 1995. Exact and approximation algorithms for sorting by reversal, with application to genome rearrangement. Algorithmica 13:180-210.

Yuusuke Kounoike, Keiichi Kaneko and Yuji Shinano, Computing the Diameters of 14- and 15-pancake Graphs, Proc. International Symposium on Parallel Architectures, Algorithms and Networks(ISPAN 2005), pp. 490-495.

Tannier, Eric and Marie-France Sagot. 2004. Sorting by reversals in subquadratic time. Proceedings of the 15th Annual Symposium on Combinatorial Pattern Matching, pp. 1-13. Berlin: Springer-Verlag.

LINKS

Table of n, a(n) for n=1..17.

M. H. Heydari and I. Hal Sudborough, On the diameter of the pancake network,J. Algorithms 25 (1997) no 1, 67-94

Marc Lebrun et al., See under V1N5

Ed Pegg Jr, Pancakes

Ivars Peterson, Pancake Sorting.

Ivars Peterson, Improved Pancake Sorting

Simon Singh, Flipping pancakes with mathematics, Blog Posting, Nov 14 2013. [States that a(18)=20, a(19)=22]

N. J. A. Sloane, My favorite integer sequences, in Sequences and their Applications (Proceedings of SETA '98).

Eric Weisstein's World of Mathematics, Pancake Sorting

Douglas B. West, The Pancake Problems (1975, 1979, 1973) - From N. J. A. Sloane, Jul 26 2012

Index entries for sequences related to sorting

FORMULA

It is known that a(n) >= n+1 for n >= 6, a(n) >= 17n/16 if n is a multiple of 16 (so a(32) >= 34) and a(n) <= (5n+5)/3.

There is an improved asymptotic upper bound of (18/11)n + O(1) for the number of prefix reversals to sort permutations of length n given in the Chitturi et al. paper. - Ivan Hal Sudborough (hal_sud(AT)yahoo.com), Jul 02 2008

CROSSREFS

Cf. A067607, A078941 and A078942.

Sequence in context: A039233 A075748 A039177 * A184431 A078358 A175968

Adjacent sequences:  A058983 A058984 A058985 * A058987 A058988 A058989

KEYWORD

nonn,nice,hard

AUTHOR

N. J. A. Sloane, Jan 17 2001, Oct 12 2007

EXTENSIONS

Typo in value for a(5) corrected by Ed Pegg Jr., Jan 02, 2002

a(14)-a(17) from Ivan Hal Sudborough (hal_sud(AT)yahoo.com), Jul 02 2008. The new upper bounds for n = 14, 15, 16 and 17 are found in the articles by Asai et al. and Kounoike et al.

Simon Singh's blog gives values for a(18) and a(19). It is not clear if these have been proved to be correct. - N. J. A. Sloane, Dec 11 2013

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified April 23 22:11 EDT 2014. Contains 240947 sequences.