煎餅排序

一次示例操作。上方是用煎饼铲子将顶上三张煎饼翻面，翻完以后变为下方所示的状态。在焦煎饼问题中，如果原来三张饼的焦面朝下，则翻完之后变为焦面朝上

煎饼排序（Template:Lang-en）指的是将大小不同的一摞煎饼按大小排序的数学问题，其中Template:Link-en每次只能从任意位置铲起上方全部煎饼并翻面。“煎饼数”（Template:Lang-en）是指给定煎饼的张数时，最坏情况下需要的最少翻面次数。这个问题最早由美国几何学家雅各布·E·古德曼提出。它属于排序问题的变种。煎饼排序的目标和传统排序算法最小化比较次数不同，因为它每次操作只允许反转序列的Template:Tsl，所以需要最小化反转前缀次数。焦煎饼排序是煎饼排序的变种问题，每张煎饼都有一面是烤焦的，最终除了按照大小排序以外还要让所有焦面向下。

煎饼问题

最初的煎饼问题

对于任意一叠Template:Math张煎饼，人们已经证明最小翻转次数在Template:Math到Template:Math之间（约为1.07n到1.64n之间），但精确值仍未知。

最简单的算法在最坏情况下需要Template:Math次翻转。这种算法是选择排序的变体，每轮用一次翻转把未排序的煎饼中最大者翻到顶上，再用一次翻转把它翻到最终所在处（目前未排序煎饼和已排序煎饼的交界处），然后对剩余未排序煎饼重复此过程。剩下两个煎饼时只需一次翻转即完成排序。

1979年比尔·盖茨和赫里斯托斯·帕帕季米特里乌给出了一个上界Template:Math。三十年后德克薩斯州大學達拉斯分校萨薄若（Sudborough）教授领导的一组研究者将这个上界改进为Template:Math。

2011年，劳伦特·比尔托（Laurent Bulteau）、纪尧姆·佛丁（Guillaume Fertin）和伊雷娜·鲁苏（Irena Rusu）证明了给定一叠煎饼的长度分布，找到最短解法是NP困难的，最终解决了这个已提出三十余年的问题。

焦煎饼问题

焦煎饼问题（Template:Lang-en）是煎饼问题的一种变体，其中每个煎饼有一面是焦的，排序后必须使所有煎饼焦的一面朝下。这是一类带符号的排列问题（Template:Lang-en），如果某个煎饼焦的一面朝上，就在排列中给它加一个符号，最后结果必须不含符号。2008年，一组本科生对大腸桿菌-{zh-cn:编程;zh-tw:程式設計;}-，构造细菌计算机让其翻转类似焦煎饼的DNA序列，解决了一个简单的焦煎饼问题。DNA具有方向性（5'端和3'端）和顺序（啟動子和编码区）。虽然细菌对DNA翻转的处理能力较弱，但单次培养中为数众多的细菌提供了庞大的并行计算平台。當细菌帶有抗生素抗藥性時，DNA序列的排序問題即告解決。

字符串中的煎饼问题

如果将煎饼摞视为一个字符串，每次翻转相当于取一段前缀并将其反转，这是一个置換操作。不过，前述讨论假定每个煎饼都是不同的，但是字符串可以包含相同字符，因此前缀反转所需次数可能会减少。赫肯斯（Hurkens）等人在2007年构造了二元和三元字符串前缀反转排序的多项式时间精确算法，并证明了用最少的前缀反转次数将一个二元字符串变换为另一个二元字符串是NP困难的。池图瑞（Chitturi）等人于2010年将上述结论推广到了一般字符串，证明了它是NP完全的，并给出了最少次数的上下界。池图瑞在2011年证明了带符号的字符串前缀反转排序（即字符串中的焦煎饼问题）也是NP完全的。

历史 

煎饼排序问题最初由Template:Tsl提出，他当时用了假名“哈利·德威特”（原文“Template:Lang”，音近“Template:Lang”，即“忙亂的侍應”）。

煎饼问题更多地在教育中见到，但也会在并行处理网络中用到，它的解答对应着处理器之间高效的最短路算法。这个问题也在计算生物学中有所应用。

微软公司创立者比尔·盖茨就这个问题在1979年发表过一篇题为《前缀逆转排序的边界问题》（Template:Lang-en）的论文，这是他唯一广为人知的数学论文。在这篇论文中盖茨描述了一种高效的煎饼排序算法。另外，《乃出個未來》的主創之一Template:Tsl研究了焦煎饼问题。他们两位的合作者分别是赫里斯托斯·帕帕季米特里乌（当时在哈佛大学任职，目前在哥伦比亚大学）与曼纽尔·布卢姆（当时在加利福尼亞大學柏克萊分校任职，目前在卡内基·梅隆大学）。

之后，相关的字符串子串反转排序问题也得到了研究。不过，带符号的子串反转排序问题有平方时间的精确算法，但（不带符号的）子串反转问题不存在多项式时间的精确算法，其多项式时间近似算法的近似因子下界为1.0008，上界为1.5，后来找到了近似因子为1.375的多项式时间近似算法。

煎饼图

煎饼图P₃

煎饼图P₄可以用4个P₃递归地构造：给每个子图编号1、2、3、4，编号为i的子图每个顶点对应的排列为1－4除去i的全排列，末尾加上i

Template:Main n-煎饼图的顶点用1到n的全排列编号，两个顶点之间有边当且仅当两个顶点对应的排列可以由前缀反转得到。它是n!个顶点的正則圖，度数为n−1。煎饼排序问题等价于求取煎饼图的直径。

n-煎饼图记为P_n，可以使用n个P_n−1递归地构建：给每个子煎饼图分别编号1、2、……、n，编号为i的子图每个顶点对应的排列为1－n这n个数除去i的全排列，末尾加上i。

三阶及以上的煎饼图围长恒为6：

$g(P_n)=6\text{, if }n>2$

P_n的亏格γ(P_n)为：

$n!\left(\frac{n-4}{6}\right)+1\le \gamma (P_n)\le n!\left(\frac{n-3}{4}\right)-\frac{n}{2}+1$

煎饼图有许多有趣的性质，例如对称性和上文所述的递归结构。另外，它是凱萊圖，因此也是Template:Tsl。随着维度的增加，煎饼图的度数和直径都以低于对数的速度增长，因此它比Template:Tsl等图更为Template:Tsl。人们对其在并行计算的互连网络模型的应用非常关注。如果把煎饼图视为互连网络的模型，它的直径大小可以衡量通信延迟高低。

相关整数序列 

给定一叠Template:Math个煎饼，有多少种长度排列可以在翻Template:Math次以内排好序

高度 Template:Math	Template:Math
	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1	1
2	1	1
3	1	2	2	1
4	1	3	6	11	3
5	1	4	12	35	48	20
6	1	5	20	79	199	281	133	2
7	1	6	30	149	543	1357	1903	1016	35
8	1	7	42	251	1191	4281	10561	15011	8520	455
9	1	8	56	391	2278	10666	38015	93585	132697	79379	5804
10	1	9	72	575	3963	22825	106461	377863	919365	1309756	814678	73232
11	1	10	90	809	6429	43891	252737	1174766	4126515	9981073	14250471	9123648	956354	6
12	1	11	110	1099	9883	77937	533397	3064788	14141929	49337252	118420043	169332213	111050066	13032704	167
13	1	12	132	1451	14556	130096	1030505	7046318	40309555	184992275	639783475	1525125357	2183056566	1458653648	186874852	2001

在整數數列線上大全中，有一些序列与煎饼排序有关：

• Template:OEIS2C – 最坏情况下需要翻的次数
• Template:OEIS2C – 有多少种煎饼长度排列是最坏情况（即上表每行最后一个数）
• Template:OEIS2C – 焦煎饼问题中最坏情况下需要翻的次数
• Template:OEIS2C – 有多少种焦煎饼长度排列是最坏情况
• Template:OEIS2C – 即将上表每一行连接起来

拓展阅读 

• Template:Cite journal
• Template:Cite journal

外部链接 

• Cut-the-Knot上的翻煎饼谜题Template:Wayback，用Java实现的煎饼问题程序，以及一些讨论。
• 道格拉斯·韦斯特讲述的煎饼问题Template:Wayback
• Template:MathWorld
• 一部小动画，演示了细菌计算机如何解决焦煎饼问题。