阅微堂BBS里判断全排列问题的讨论
题目：给一个n长的数组，判断它是否为一个1,2,...,n的全排列，要求在线性时间，常数空间内实现。
今天和同学讨论了下，他给出的做法等价于"给定n长的数组，不用额外空间，通过交换元素，在线性时间里把数组排序，然后就能判断该数组是否为全排列"。这不难想出，但我不认同这种方法是常数空间，因为存放这些数组的空间就是O(n)空间。
我把实现的程序看成是一个黑盒子，既然是常数空间，那么盒子的体积就是固定，不随n变化。n长的数组相当于一个输入流作为参数输入到函数。输入完之后函数判断该序列是否为全排列。形象地表示为：
可假定这些数都落在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不需要去记录已读取的数是什么，只需要把它们投影到某个常数空间的"点"上，当所有的数读完，再来判断该点的性质，就可以得出结论。这样的数学函数存不存在，难说。
转载请注明：来自pugWoo's Life
本文地址：http://www.pugwoo.com/2009/12/29/quan-pai-xu.html
8 条评论
我要留言kangzj 发表于 2009-12-30 at 11:15 回复 引用
前一半看懂了
pugwoo 发表于 2009-12-30 at 12:57 回复 引用
到推出该实现到“最后时刻”才能判断结果应该还好吧，希望没推错。其实我更倾向于证明常数空间是不可能的，但没有证据，找不到不代表不存在~~
zhiqiang 发表于 2009-12-30 at 14:56 回复 引用
给的数并不是保存在一个数组里，而是以一个问答机（Oracle）的形式给出来，当你需要知道数组里的数是第几个数的时候，向Oracle查询，然后Oracle返回数据给你。
问题的理论意义是：全排列问题是否属于Log-Space的问题，介绍见 http://en.wikipedia.org/wiki/L_(complexity)
GEZ鸽子 发表于 2009-12-30 at 14:56 回复 引用
zhiqiang 发表于 2009-12-30 at 14:57 回复 引用
pugwoo 发表于 2009-12-30 at 23:08 回复 引用
呵呵，胡思乱想啦
pugwoo 发表于 2009-12-30 at 23:11 回复 引用
谢谢老大指导，你一直是我奋斗的目标阿~
其实我想的时候感觉到是log n了，我举的判断一排数奇数和偶数的个数是否相等的例子，就是log n，我在等有谁反驳我我就说放松条件到log n，全排序的问题还是难以断定阿