Name
Abstract | ||
|---|---|---|
A stack of n pancakes can be rearranged in all n! ways by a sequence of n!−1 flips, and a stack of n ‘burnt’ pancakes can be rearranged in all 2nn! ways by a sequence of 2nn!−1 flips. In both cases, a computer program can efficiently generate suitable solutions. We approach these tasks instead from a human perspective. How can we determine the next flip directly from the current stack? How can we flip the minimum or maximum number of (burnt) pancakes overall? What if we are only allowed to flip the top n−2, n−1, or n (burnt) pancakes? We answer the first question with simple successor rules that take worst-case O(n)-time and amortized O(1)-time. Then we answer the second question exactly for minimization, and provide conjectures for maximization. For the third question, we prove that solutions almost certainly exist for pancakes and burnt pancakes using only these three flips. More broadly, we discuss how efficiency and optimality can shape iterative solutions to Hamilton cycle problems in highly symmetric graphs. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.tcs.2015.09.007 | Theoretical Computer Science |
Keywords | Field | DocType |
Pancake sorting,Greedy algorithm,Permutations,Signed-permutations,Prefix-reversal,Symmetric group,Cayley graph,Hamilton cycle,Human problem solving | Discrete mathematics,Combinatorics,Symmetric group,Hamiltonian path,Successor cardinal,Cayley graph,Permutation,Greedy algorithm,Minification,Mathematics,Pancake sorting | Journal |
Volume | Issue | ISSN |
609 | P1 | 0304-3975 |
Citations | PageRank | References |
0 | 0.34 | 29 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Joe Sawada | 1 | 36 | 9.42 |
| Aaron Williams | 2 | 139 | 20.42 |