Successor rules for flipping pancakes and burnt pancakes

DOI10.1016/j.tcs.2015.09.007zbMath1332.68091OpenAlexW1886146870MaRDI QIDQ897860

N. E. Zubov

Publication date: 8 December 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.09.007

zbMATH Keywords

permutationsCayley graphgreedy algorithmsymmetric groupHamilton cycleprefix-reversalpancake sortinghuman problem solvingsigned-permutations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Permutations, words, matrices (05A05) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Eulerian and Hamiltonian graphs (05C45)

Related Items

Greedy flipping of pancakes and burnt pancakes ⋮ Hamiltonicity of \(k\)-sided pancake networks with fixed-spin: efficient generation, ranking, and optimality ⋮ A Hamilton cycle in the \(k\)-sided pancake network

Uses Software

• OEIS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Greedy flipping of pancakes and burnt pancakes
• A Gray code for fixed-density necklaces and Lyndon words in constant amortized time
• Efficient oracles for generating binary bubble languages
• The coolest way to generate binary strings
• Pancake flipping is hard
• A surprisingly simple de Bruijn sequence construction
• On average and highest number of flips in pancake sorting
• Binary bubble languages and cool-lex order
• A new algorithm for generation of permutations
• An \((18/11)n\) upper bound for sorting by prefix reversals
• The coolest way to generate combinations
• A method and two algorithms on the theory of partitions
• Pancake problems with restricted prefix reversals and some corresponding Cayley networks.
• Ranking and unranking permutations in linear time
• Shorthand universal cycles for permutations
• On the problem of sorting burnt pancakes
• Cool-lex order and \(k\)-ary Catalan structures
• De Bruijn Sequences for Fixed-Weight Binary Strings
• An explicit universal cycle for the ( n -1)-permutations of an n -set
• Transforming cabbage into turnip
• On the Diameter of the Pancake Network