Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419204 | Discrete Applied Mathematics | 2016 | 14 Pages |
Abstract
We prove that a stack of nn pancakes is rearranged in all n!n! ways by repeatedly applying the following rule: Flip the maximum number of pancakes that gives a new stack. This complements the previously known pancake flipping Gray code (Zaks, 1984) which we also describe as a greedy algorithm: Flip the minimum number of pancakes that gives a new stack . Surprisingly, these maximum and minimum flip algorithms also rearrange stacks of nn ‘burnt’ pancakes in all 2nn!2nn! ways. We conjecture that these four algorithms are essentially the only greedy algorithms for rearranging pancakes and burnt pancakes in all possible ways using flips.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Joe Sawada, Aaron Williams,