翻煎饼问题——前缀翻转排序问题

偶然看到编程之美里的一道关于翻煎饼的算法题里的注解。原来这是大名鼎鼎的比尔盖茨的大学论文《Bounds for Sorting by Prefix Reversal》研究的问题。于是索性翻来看看,顺便随手翻译。


引言:

在这篇文章中,我们先推演fn的上下界。一定的界限在当下已经知道了。比如,对于任意一堆的煎饼。 相邻关系是指一对在堆中相邻的煎饼,这样的两个煎饼之间没有任何的空间。如果,最大的煎饼在最底端,那么这算作一个额外的临近关系。那么,对于n>=4,存在没有任何相邻关系的饼堆。另外,一个排序的堆一定有n个相邻关系,并且每一次翻转可以创建至多一个相邻关系。因此,对于n>=4,fn>=n 在第二部分,我们会证明fn的有上界(5n+5)/3,通过设计一种至少性能好的排序算法。在第三部分,我们指出,fn有17n/16的下界,通过构造,k>=1,一个大小为16k的堆需要17k次移动来达到有序。最后,在第四部分,我们推演出fn在煎饼需要单序有序的更强限制下,fn的界限。也就是说,每个煎饼至少得翻转偶数次数。对于这个修改问题的上下界,也给出了。

正文:

算法:

几个定义:
Sn: Sigma(n)*里的字符串的任意排列, 其中Sigma(n)是集合{1,2,…,n}
Sn上的二元关系–>: pi–>sigma,其中pi是Sigma(n)*中的某两个字符串x,y的连接,sigma是x的逆字符串和y的连接
f(pai): pai是一种字符串排列,那么f(pai)则是最小的次数k,使得存在一种排列顺序使得pai能通过–>运算,变成en,其中en是n上的identity permutation(类似于按照整数的递增序列排序)
f(n): 是在Sn上的最大的f(pai)

pai中的相邻关系: Sn中的一种字符串排列,如果pai中的第j位数字和第j+1位数字的差的绝对值为1,那么则说j和j+1相邻。
block: 对于pai=xby的三者连接,如果所有从x到y之间的字符子串b中所有的pair都有相邻关系,并且b是满足此性质的pai中的最长子串,那么b被称为一个block
free: 如果pai中的第j位字符,对于前后的pair都没有相邻关系,那么pai(j)是free的
*注释: 在此文中,把1和n也看做相邻的??????????????????

讨论:

我们呈现了一种算法用来排序任意长度为n的排列用大概5n/3次前序翻转。改进乘数的常数项似乎非常具有挑战。我们还描述了一种用来达到更小fn下界的方法,并且展示了它如何用来证明fn有17n/16的下界。改进这一下界,似乎看起来并不复杂。事实上,我们猜想,对于”hard”排列x,fx等于19n/16。并且,更小的下界可以通过引入不同的T来证明达到。但是,我们不知道这一上下界如何被更大幅度地缩小。很自然地可以看出,fn/n收敛并不明显,所以也有可能并不会有更好的界限可以被达到。

Advertisements

One thought on “翻煎饼问题——前缀翻转排序问题

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s