输入: 一个包含整数值1到N(某些整数值可以出现多次!)的只读长度为N的数组和一个固定大小(10,100,1000等 - 不取决于 N)的内存区域。
如何在O（n）的时间复杂度下确定该数组是否表示排列？
--到目前为止我所获得的（一个答案证明这是不好的）：
我知道如果条件（2）成立，我可能会有一个排列。 我想知道是否有办法证明条件（2）足以告诉我是否有一个排列。 到目前为止，我还没有弄清楚...
我稍微怀疑是否有一个解决方案。你的问题似乎与几年前在数学文献中提出的问题非常接近，其中这里给出了一个摘要（“重复检测问题”，S. Kamal Abdali，2003）使用了循环检测--其思想如下：
如果存在重复项，则存在一个介于1和N之间的数字j，使得以下内容会导致无限循环：
x := j;
do
{
x := a[x];
}
while (x != j);
Abdali使用一种查找重复项的方法。基本上，以下算法（使用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上询问，那里有一些有趣的讨论。
is_duplicate(a, N, j) 应该在 j 是重复项时返回 true，那么它的返回条件不应该是 return (x1 == j) 吗？ - dark_prince这是不可能在O(1)空间内完成的，至少需要使用单扫描算法。
证明
假设您已经处理了N/2个元素。 假设序列是一个排列，则给定算法的状态，您应该能够找出剩余的N/2个元素的集合。 如果无法找出剩余的元素，则算法可以通过重复一些旧元素来欺骗它。
有N中N/2种可能的剩余集。 每个剩余集必须由算法的不同内部状态表示，否则您无法找出剩余的元素。 但是，要存储X个状态需要对数空间，因此需要BigTheta(log(N choose N/2))空间来存储N选择N/2个状态。 随着N增长，该值也增长，因此算法的内部状态不能适合于O(1)空间。
更正式的证明
您想创建一个程序P，该程序在处理了N/2个元素后，给定最终的N/2个元素和线性时间常量空间算法的内部状态，确定整个序列是否为1..N的排列。 对此次要求二次程序没有时间或空间限制。
假设P存在，我们可以创建一个程序Q，仅使用线性时间常量空间算法的内部状态，它确定序列的必要最终N/2个元素（如果它是排列）。 Q通过将每个可能的最终N/2个元素传递给P，并返回P返回真的集合来工作。
但是，由于Q具有N选择N/2种可能的输出，因此它必须具有至少N选择N/2个可能的输入。 这意味着原始算法的内部状态必须存储至少N选择N/2个状态，需要BigTheta(log N choose N/2)的空间，这大于恒定的大小。
因此，如果具有恒定大小的内部状态，则原始算法也无法正常工作。
[我认为这个想法可以推广，但思考并不能证明]
后果
BigTheta(log(N choose N/2))等价于BigTheta(N)。因此，仅使用布尔数组并在遇到值时进行标记（可能）是空间和时间上的最优解决方案，因为它需要线性时间。
O(N)时间内解决。你怎么知道不存在一种策略，在列表的N/2位置，你可能仍然需要重新访问列表的早期部分来处理剩下的部分？只要你不那么频繁地这样做，它仍然可以是O(N)。 - Rex Kerr我怀疑你能够证明那件事 ;)
(1, 2, 4, 4, 4, 5, 7, 9, 9)
我认为更一般地说，这个问题不能通过按顺序处理数字来解决。假设您按顺序处理元素，并且您已经处理了数组的一半。现在，您的程序状态必须反映出到目前为止遇到的数字。这至少需要O（n）位来存储。
http://en.wikipedia.org/wiki/Bloom_filter
对于数组中的每个元素
运行k个哈希函数
检查布隆过滤器中是否包含该元素
如果存在，则有一定概率之前已经看到该元素
如果不存在，则将其添加进去
完成后，你也可以将结果与按顺序排列的1..N数组的结果进行比较，因为这样只需要再花费N。
现在，如果我没有提供足够的警告，那么它并不是100%准确的，甚至不接近，因为你指定了复杂度为N，这意味着N>>M, 因此从根本上讲，这种方法无法按照你的规定工作。
顺便说一下，单个项的误报率应该为
e = 2^(-m/(n*sqrt(2)))
调整它将会给你一个大致的想法，M需要多大才能被接受。
我不知道如何以O(N)的时间复杂度完成它，甚至不确定是否可以用O(N)的时间复杂度完成。如果使用适当的排序和比较，我知道可以在O(N log N)的时间复杂度内完成。
话虽如此，有许多O(N)的技术可以用来证明一个序列不是另一个序列的排列。
希望这能帮到你。
你可以通过计算sum(x_i)和product(x_i)模一堆不同随机选定大小为O(n)的常数C，以随机化的方式在O(n)时间和常量空间内完成此操作。这基本上解决了product(x_i)过大的问题。
然而，仍然存在许多未解决的问题，例如如果sum(x_i)=N(N+1)/2和product(x_i)=N!是保证排列的充分条件，以及非排列生成假阳性的几率是多少（我希望每次尝试的C的几率约为1/C，但也许不是）。
public static boolean isPermutation(int[] array) {
boolean result = true;
array = removeDuplicates(array);
int startValue = 1;
for (int i = 0; i < array.length; i++) {
if (startValue + i != array[i]){
return false;
}
}
return result;
}
public static int[] removeDuplicates(int[] input){
Arrays.sort(input);
List<Integer> result = new ArrayList<Integer>();
int current = input[0];
boolean found = false;
for (int i = 0; i < input.length; i++) {
if (current == input[i] && !found) {
found = true;
} else if (current != input[i]) {
result.add(current);
current = input[i];
found = false;
}
}
result.add(current);
int[] array = new int[result.size()];
for (int i = 0; i < array.length ; i ++){
array[i] = result.get(i);
}
return array;
}
public static void main (String ... args){
int[] input = new int[] { 4,2,3,4,1};
System.out.println(isPermutation(input));
//output true
input = new int[] { 4,2,4,1};
System.out.println(isPermutation(input));
//output false
}
好的，这有些不同，但似乎可以工作！
我运行了这个测试程序（C#）：
static void Main(string[] args) {
for (int j = 3; j < 100; j++) {
int x = 0;
for (int i = 1; i <= j; i++) {
x ^= i;
}
Console.WriteLine("j: " + j + "\tx: " + x + "\tj%4: " + (j % 4));
}
}
bool IsPermutation = false;
switch (j % 4) {
case 0:
IsPermutation = (x == j);
break;
case 1:
IsPermutation = (x == 1);
break;
case 2:
IsPermutation = (x == j + 1);
break;
case 3:
IsPermutation = (x == 0);
break;
}
现在我承认这可能需要一些微调。它不是100％的，但这是一个很好的简单方法来开始。也许通过在XOR循环中运行一些小检查，这可以被完善。尝试从那里开始。
请查看以下解决方案。它使用了O(1)的额外空间。 在检查过程中，它会更改数组，但在最后将其返回到初始状态。
思路如下：
按顺序遍历数字（现在所有数字都保证在范围[1, n]内），对于每个数字x（例如3）：
这样，我们确信所有元素都在范围[1, n]内，并且没有重复项 => 数组是一个排列。
int is_permutation_linear(int a[], int n) {
int i, is_permutation = 1;
// Step 1.
for (i = 0; i < n; ++i) {
if (a[i] < 1 || a[i] > n) {
return 0;
}
}
// Step 2.
for (i = 0; i < n; ++i) {
if (a[abs(a[i]) - 1] < 0) {
is_permutation = 0;
break;
}
a[i] *= -1;
}
// Step 3.
for (i = 0; i < n; ++i) {
if (a[i] < 0) {
a[i] *= -1;
}
}
return is_permutation;
}
这是完整的测试程序：
/*
* is_permutation_linear.c
*
* Created on: Dec 27, 2011
* Author: Anis
*/
#include <stdio.h>
int abs(int x) {
return x >= 0 ? x : -x;
}
int is_permutation_linear(int a[], int n) {
int i, is_permutation = 1;
for (i = 0; i < n; ++i) {
if (a[i] < 1 || a[i] > n) {
return 0;
}
}
for (i = 0; i < n; ++i) {
if (a[abs(a[i]) - 1] < 0) {
is_permutation = 0;
break;
}
a[abs(a[i]) - 1] *= -1;
}
for (i = 0; i < n; ++i) {
if (a[i] < 0) {
a[i] *= -1;
}
}
return is_permutation;
}
void print_array(int a[], int n) {
int i;
for (i = 0; i < n; i++) {
printf("%2d ", a[i]);
}
}
int main() {
int arrays[9][8] = { { 1, 2, 3, 4, 5, 6, 7, 8 },
{ 8, 6, 7, 2, 5, 4, 1, 3 },
{ 0, 1, 2, 3, 4, 5, 6, 7 },
{ 1, 1, 2, 3, 4, 5, 6, 7 },
{ 8, 7, 6, 5, 4, 3, 2, 1 },
{ 3, 5, 1, 6, 8, 4, 7, 2 },
{ 8, 3, 2, 1, 4, 5, 6, 7 },
{ 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 8, 4, 2, 1, 3, 5, 6 } };
int i;
for (i = 0; i < 9; i++) {
printf("array: ");
print_array(arrays[i], 8);
printf("is %spermutation.\n",
is_permutation_linear(arrays[i], 8) ? "" : "not ");
printf("after: ");
print_array(arrays[i], 8);
printf("\n\n");
}
return 0;
}
并且它的输出为：
array: 1 2 3 4 5 6 7 8 is permutation.
after: 1 2 3 4 5 6 7 8
array: 8 6 7 2 5 4 1 3 is permutation.
after: 8 6 7 2 5 4 1 3
array: 0 1 2 3 4 5 6 7 is not permutation.
after: 0 1 2 3 4 5 6 7
array: 1 1 2 3 4 5 6 7 is not permutation.
after: 1 1 2 3 4 5 6 7
array: 8 7 6 5 4 3 2 1 is permutation.
after: 8 7 6 5 4 3 2 1
array: 3 5 1 6 8 4 7 2 is permutation.
after: 3 5 1 6 8 4 7 2
array: 8 3 2 1 4 5 6 7 is permutation.
after: 8 3 2 1 4 5 6 7
array: 1 1 1 1 1 1 1 1 is not permutation.
after: 1 1 1 1 1 1 1 1
array: 1 8 4 2 1 3 5 6 is not permutation.
after: 1 8 4 2 1 3 5 6
如果数组中没有重复的值，那么它就是一个排列，可以很容易地在O(N)时间内检查。
N!所需的存储空间，严格来说取决于N。而且严格来说，在O(N)的时间内无法对N个数字进行乘法运算。 - polygenelubricantsm个数中的n个，并停止了你的算法。现在你可以（虽然需要一些时间）通过处理任何一个由n-m个数字组成的流并查看何时出现排列来确定你已经看到了哪m个数字。因此从信息的角度来看，你已经存储了所有的数字m，因此必须使用线性内存。 - Thomas Ahle