INS*_*INS 39 arrays algorithm permutation
输入:包含从1到N的整数值的N个元素的只读数组(某些整数值可以出现多次!).和固定大小的存储区(10,100,1000等 - 不依赖于N).
如何在O(n)中判断数组是否代表一个排列？
-什么我实现了迄今(答案证明,这是不是好): -
我知道如果条件(2)为真,我可能会有一个排列.我想知道是否有办法证明条件(2)足以判断我是否有排列.到目前为止,我还没想出来......
Jas*_*n S 16
我有点怀疑有一个解决方案.你的问题似乎与几年前在数学文献中提出的问题非常接近,这里给出的摘要("重复检测问题",S.Kamal Abdali,2003)使用循环检测 - 这个想法如下:
如果存在重复,则存在j介于1和N之间的数字,以便以下将导致无限循环:
x := j;
do
{
x := a[x];
}
while (x != j);
因为置换由不同元素s 0,s 1,... s k-1的一个或多个子集S组成,其中对于1和k-1之间的所有j ,s j = a [s j-1 ],并且s 0 = a [s k-1 ],因此所有元素都涉及周期 - 其中一个重复项不会成为这样一个子集的一部分.
例如,如果该数组= [2,1,4,6,8,7,9,3,8]
然后在位置5处以粗体显示的元素是重复的,因为所有其他元素形成循环:{2 - > 1,4 - > 6 - > 7 - > 9 - > 8 - > 3}.阵列[2,1,4,6,5,7,9,3,8]和[2,1,4,6,3,7,9,5,8]是有效排列(周期为{2} - > 1,4 - > 6 - > 7 - > 9 - > 8 - > 3,5}和{2 - > 1,4 - > 6 - > 7 - > 9 - > 8 - > 5 - > 3}分别).
阿卜达利进入了寻找重复的方式.基本上,以下算法(使用Floyd的循环查找算法)可以在您遇到的其中一个重复项中发生:
function is_duplicate(a, N, j)
{
/* assume we've already scanned the array to make sure all elements
are integers between 1 and N */
x1 := j;
x2 := j;
do
{
x1 := a[x1];
x2 := a[x2];
x2 := a[x2];
} while (x1 != x2);
/* stops when it finds a cycle; x2 has gone around it twice,
x1 has gone around it once.
If j is part of that cycle, both will be equal to j. */
return (x1 != j);
}
困难在于我不确定你所说的问题是否与他论文中的问题相符,而且我也不确定他描述的方法是在O(N)中运行还是使用固定数量的空间.一个潜在的反例是以下数组:
[3,4,5,6,7,8,9,10 ...... N-10,N-9,N-8,N-7,N-2,N-5,N-5,N- 3,N-5,N-1,N,1,2]
这基本上是身份置换移动了2,元素[N-6,N-4和N-2]被[N-2,N-5,N-5]取代.这有正确的总和(不是正确的产品,但我拒绝将产品作为一种可能的检测方法,因为用任意精度算术计算N!的空间要求是O(N),这违反了"固定存储空间"的精神.要求),如果你试图寻找周期,你将获得周期{3 - > 5 - > 7 - > 9 - > ... N-7 - > N-5 - > N-1}和{4 - > 6 - > 8 - > ... N-10 - > N-8 - > N-2 - > N - > 2}.问题是可能有多达N个周期(身份置换有N个周期),每个周期都占用O(N)来找到重复,你必须跟踪某些已经跟踪的周期和哪些没有.一世' 我怀疑在固定的空间内可以做到这一点.但也许是.
这是一个足够严重的问题,值得在mathoverflow.net上询问(尽管大多数时候mathoverflow.net都是在stackoverflow上引用的,但是这些问题太容易了)
编辑:我确实问过mathoverflow,那里有一些有趣的讨论.
Cra*_*ney 10
这在O(1)空间中是不可能的,至少使用单扫描算法.
证明
假设您已经处理了N个元素中的N/2个.假设序列是一个置换,那么,给定算法的状态,你应该能够找出N/2个剩余元素的集合.如果你无法找出剩余的元素,那么可以通过重复一些旧元素来欺骗算法.
N选择N/2个可能的剩余集.它们中的每一个都必须由算法的不同内部状态表示,否则你无法找出剩余的元素.但是,它需要对数空间来存储X状态,因此需要BigTheta(log(N选择N/2))空间来存储N选择N/2个状态.该值随N增长,因此算法的内部状态不适合O(1)空间.
更正式的证明
你想创建一个程序P,给定最后的N/2个元素和线性时间常数空间算法在处理N/2个元素后的内部状态,确定整个序列是否为1的置换. .N.此次要计划没有时间或空间限制.
假设P存在,我们可以创建一个程序Q,只采用线性时间常数空间算法的内部状态,该算法确定序列的必要最终N/2个元素(如果它是一个置换).Q通过传递P每个可能的最终N/2个元素并返回P返回true的集合.
但是,因为Q有N选择N/2个可能的输出,所以它必须至少有N个选择N/2个可能的输入.这意味着原始算法的内部状态必须存储至少N个选择N/2个状态,需要BigTheta(log N选择N/2),这大于常数大小.
因此,如果具有恒定大小的内部状态,则具有时间和空间界限的原始算法也不能正确地工作.
[我认为这个想法可以概括,但思考并没有证明.]
后果
BigTheta(log(N选择N/2))等于BigTheta(N).因此,只需使用布尔数组并在遇到它们时勾选值(可能)是空间最优的,并且时间也是最佳的,因为它需要线性时间.
我怀疑你能否证明这一点;)
(1, 2, 4, 4, 4, 5, 7, 9, 9)
我认为更一般地说,这个问题不能通过按顺序处理数字来解决.假设您按顺序处理元素,并且您在数组的中间.现在你的程序状态必须以某种方式反映你到目前为止遇到的数字.这需要至少O(n)位来存储.