pugWoo's Life   All-Posts  About

阅微堂BBS里判断全排列问题的讨论

题目:给一个n长的数组,判断它是否为一个1,2,…,n的全排列,要求在线性时间,常数空间内实现。

今天和同学讨论了下,他给出的做法等价于”给定n长的数组,不用额外空间,通过交换元素,在线性时间里把数组排序,然后就能判断该数组是否为全排列”。这不难想出,但我不认同这种方法是常数空间,因为存放这些数组的空间就是O(n)空间。

我把实现的程序看成是一个黑盒子,既然是常数空间,那么盒子的体积就是固定,不随n变化。n长的数组相当于一个输入流作为参数输入到函数。输入完之后函数判断该序列是否为全排列。形象地表示为:

2009-12-29 22-59-25.png

可假定这些数都落在1到n范围内,否则可以即刻检测出不是全排列。接着,可以推导出这个函数应该在”最后时刻”才能判断出是否为全序列。这里指的”最后时刻”包括那些肉眼轻易就能判别的情况,比如输入1、1、2、4…,一开始出现了两个1,我们马上就能判断该序列不是全排列,但这个实现不能具有这样的功能。

假设该实现能在当出现两个数重复时,就判断出结果。那么,我们可以利用该函数的常数空间,构造出一个可以存储无限信息的有限空间。假设对于信息111000…101,不管它多长,它的左边第一位用全排序的1和2表示,1表示0,2表示1;第二位用全排序的3和4表示,3表示0,4表示1. 以此类推,则这则信息相当于往Function输入2、4、6、7、9、10….这样的一排数。如果该实现能在第一次出现重复时就判断出是否全排列,那么可以利用该特点,随便读取出信息的任何一位,比如读取第一位,只需要往Function输入2,如果它判断出”非全排列”,则说明第一位是1. 由于Function的空间是常数的,每次读取一个bit,都可以保持Function的状态,读取后还原。就这样,我们构造了一个可写可读的可存放无穷容量的常数空间。这可能吗?

我先假定有限容量存无穷信息是不可能的。那么就可得出该函数”最后时刻”方可判断结果,无论序列是什么(无论多显而易见)。

讨论到这,我同学提出,那无论什么实现肯定都不可能是常数空间的,因为它肯定和输入长度N有关。其实常数空间的例子很多,比如说,输入一排整数,判断奇数和偶数的个数是否相等;判断是否出现了0;判断其和是否大于某个给定的数。这些简单的例子都是线性时间+常数空间就可实现的。它们有什么共同点呢?它们的输入都是随N变换的,但是输出仅是这排序列的某个属性!而这个属性反推不出原序列,即它们不可逆,结论仅是原序列性质的一个提取。

那么,判断一排数是否为全排列也仅是这排数的一个性质,知道它是不是全排列并不能反推出原来这排数的顺序,也就是这个Function提取了数列的一个性质。至于提取这个性质可不可以是常数空间呢?需要讨论。可以把这个Function看成是一种投影,它把不管多长的线,投影成一个点,这个点就是要提取的属性。前面的常数空间例子都没问题,那提取是否为全排序这个性质又能不能是常数空间呢?不好证明,或许它真的存在。

“最后时刻”方可判断结果,意味着该Function不需要去记录已读取的数是什么,只需要把它们投影到某个常数空间的”点”上,当所有的数读完,再来判断该点的性质,就可以得出结论。这样的数学函数存不存在,难说。