如何判断一个数组是否是 O(n) 的排列？

Question

输入：由 N 个元素组成的只读数组，其中包含从 1 到 N 的整数值（某些整数值可以出现多次！）。以及固定大小的内存区域（10、100、1000 等 - 不取决于 N）。

如何在 O(n) 中判断数组是否表示排列？

-- 到目前为止我所取得的成就（一个答案证明这是不好）：--

1. 我使用有限的内存区域来存储数组的和与乘积。
2. 我将总和与 N*(N+1)/2 进行比较，并将乘积与 N! 进行比较，

我知道如果条件 (2) 为真，我可能< /strong> 有一个排列。我想知道是否有一种方法可以证明条件（2）足以判断我是否有排列。到目前为止我还没弄清楚...

Answer 1

我有点怀疑是否有解决方案。您的问题似乎与几年前在数学文献中提出的问题非常接近，其中给出了 的摘要这里（“重复检测问题”，S. Kamal Abdali，2003）使用循环检测——其想法如下：

如果存在重复，则存在一个数字j 1 和 N 之间，这样以下情况将导致无限循环：

x := j;
do
{
   x := a[x];
}
while (x != j);

因为排列由不同元素 s₀, s₁, 的一个或多个子集 S 组成。 .. s_k-1 其中 s_j = a[s_j-1] 对于 1 和 k-1 之间的所有 j，并且 s ₀ = 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 -> 7 -> 3, 5 } 和 { 1, 4 -> 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 上提问< /a>，那里有一些有趣的讨论。

Answer 2

这在 O(1) 空间中是不可能做到的，至少对于单扫描算法来说是这样。

证明

假设您已经处理了 N 个元素中的 N/2 个。假设序列是一个排列，那么根据算法的状态，您应该能够算出 N/2 个剩余元素的集合。如果你无法找出剩余的元素，那么算法可能会通过重复一些旧的元素而被愚弄。

有 N 个选择 N/2 可能的剩余集合。它们中的每一个都必须由算法的不同内部状态表示，因为否则您无法计算出剩余的元素。然而，存储 X 个状态需要对数空间，因此需要 BigTheta(log(N select N/2)) 空间来存储 N select 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 select N/2)) 等于 BigTheta(N)。因此，仅使用布尔数组并在遇到它们时勾选值（可能）是空间最优的，而且也是时间最优的，因为它需要线性时间。

Answer 3

我怀疑你能否证明这一点；）

  (1, 2, 4, 4, 4, 5, 7, 9, 9)

我认为更一般地说，这个问题不能通过按顺序处理数字来解决。假设您正在按顺序处理元素并且位于数组的中间。现在你的程序的状态必须以某种方式反映你到目前为止遇到的数字。这需要至少 O(n) 位来存储。

Answer 4

这是行不通的，因为复杂性是作为 N 而不是 M 的函数给出的，这意味着 N >>> M

这是我的尝试，但是要使布隆过滤器发挥作用，您需要一个大 M，此时您也可以对整数之类的东西使用简单的位切换

http://en.wikipedia.org/wiki/Bloom_filter

对于数组中的每个元素
运行 k 个哈希函数
检查是否包含在布隆过滤器中
如果存在，则您以前可能见过该元素
如果不是，请添加它。

完成后，您也可以按顺序将其与 1..N 数组的结果进行比较，因为这只会让您再花费 N。

现在，如果我还没有输入足够的需要注意的是，它不是 100%，甚至不是 100%，因为您在 N 中指定了复杂性，这意味着 N >>> M，所以从根本上来说它不会像你指定的那样工作。

顺便说一句，单个项目的误报率应该是
e = 2^(-m/(n*sqrt(2)))

胡搞一下会让你知道 M 需要有多大才可以接受。

Answer 5

我不知道如何在 O(N) 内完成它，或者即使它可以在 O(N) 内完成。我知道如果你（使用适当的）排序和比较，它可以在 O(N log N) 中完成。

话虽这么说，有许多 O(N) 技术可以用来证明一种技术不是另一种技术的排列。

1. 检查长度。如果不相等，显然不是排列。
2. 创建 XOR 指纹。如果所有元素异或在一起的值不匹配，则它不能是排列。然而，一场比赛并没有结果。
3. 求所有元素的总和。尽管结果可能会溢出，但在匹配此“指纹”时不必担心。然而，如果您执行了涉及乘法的校验和，那么溢出将是一个问题。

希望这有帮助。

Answer 6

您可以通过计算 sum(x_i) 和 product(x_i) 模，在随机 O(n) 时间和常数空间内完成此操作一堆不同的随机选择的大小O(n)的常量C。这基本上可以解决 product(x_i) 变得太大的问题。

不过，仍然有很多悬而未决的问题，例如 sum(x_i)=N(N+1)/2 和 product(x_i)=N! 是否是充分条件保证排列，以及非排列产生误报的可能性有多大（我希望你尝试的每个 C 都有~1/C，但也许不会）。

Answer 7

当且仅当数组中没有重复值时，它才是一个排列，应该很容易在 O(N) 中检查这一点

Answer 8

根据您拥有多少空间（相对于 N），您可以尝试使用散列和存储桶。

也就是说，迭代整个列表，对每个元素进行哈希处理，并将其存储在存储桶中。您需要找到一种方法来减少哈希中的存储桶冲突，但这是一个已解决的问题。

如果一个元素试图进入一个与它相同的项目的存储桶，那么它就是一个排列。

这种类型的解决方案的复杂度为 O(N)，因为每个元素仅接触一次。

然而，这样做的问题是空间M是否大于N。如果M> N，这个解决方案就可以了，但是如果M < N，那么你将无法100%准确地解决问题。

Answer 9

首先，从信息论角度解释为什么这可能是可能的。我们可以简单地检查数组中的数字是否在 O(N) 时间和 O(1) 空间的范围内。要指定任何此类界内数字数组，需要 N log N 位信息。但指定排列需要大约 (N log N) - N 位信息（斯特林近似）。因此，如果我们在测试过程中能够获取N位信息，我们也许就能知道答案。这在 N 时间内完成是微不足道的（事实上，使用 M 静态空间，我们可以很容易地获取每步的 log M 信息，并且在特殊情况我们可以获取log N信息）。

另一方面，我们只能在静态存储空间中存储类似M log N位的信息，这可能比N少得多，所以这在很大程度上取决于决策面的形状在“排列”和“非排列”之间是什么。

我认为这几乎是可能的，但考虑到问题的设置还不太可能。我认为“应该”使用循环技巧（如 Iulian 提到的链接中所示），但是手中有尾巴的关键假设在这里失败了，因为您可以索引具有排列的数组。

Answer 10

总和和乘积不能保证正确的答案，因为这些散列会发生冲突，即不同的输入可能会产生相同的结果。如果您想要一个完美的哈希值，一个实际上完全描述数组的数字组成的单个数字结果，它可能如下。

想象一下，对于 [1, N] 范围内的任何数字 i，您都可以生成唯一的质数 P(i)（例如，< code>P(i) 是第 i 个质数）。现在您需要做的就是计算数组中所有数字的所有 P(i) 的乘积。该产品将完整且明确地描述数组的组成，而忽略数组中值的顺序。您需要做的就是预先计算“完美”值（对于排列）并将其与给定输入的结果进行比较:)

当然，这样的算法并不能立即满足发布的要求。但同时它在直观上太通用了：它允许您检测数组中绝对任何数字组合的排列。在您的情况下，您需要检测特定组合 1, 2, ..., N 的排列。也许这可以以某种方式用来简化事情......可能不是。

Answer 11

好吧，这是不同的，但它似乎有效！

我运行了这个测试程序（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));
        }
    }

简短说明：x 是单个列表的所有 XOR 的结果，i 是特定列表中的元素，j 是列表的大小。由于我所做的只是异或，因此元素的顺序并不重要。但我正在研究应用此方法时正确的排列是什么样的。

如果您查看 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 循环中运行一些小的检查，这可以得到完善。尝试从附近的某个地方开始。

Answer 12

它看起来像是要求使用堆栈机在数组中查找重复项。

当您提取每个数字并且对取出的数字了解有限时，听起来不可能知道堆栈的完整历史记录。

Answer 13

这是无法完成的证明：

假设通过某种技巧，您在除最后一个单元格之外的所有单元格中都没有检测到重复项。然后问题就简化为检查最后一个单元格是否包含重复项。

如果到目前为止您没有问题状态的结构化表示，那么您只能对每个单元格的整个先前输入执行线性搜索。很容易看出这如何让您得到二次时间算法。

现在，假设通过一些巧妙的数据结构，您实际上知道您希望最后看到哪个数字。那么当然，该知识至少需要足够的位来存储您寻找的数字——也许是一个存储单元？但是存在一个倒数第二个数字和一个倒数第二个子问题：那么您必须类似地表示一组尚未看到的两个可能的数字。这肯定比仅对剩余的一个数字进行编码需要更多的存储空间。通过一系列类似的论证，状态的大小必须随着问题的大小而增长，除非您愿意接受二次时间的最坏情况。

这就是时间和空间的权衡。您可以拥有二次时间和常数空间，或线性时间和线性空间。你不可能拥有线性时间和恒定空间。

Answer 14

查看以下解决方案。它使用 O(1) 额外 空间。
它在检查过程中更改数组，但在最后将其返回到其初始状态。

想法是：

1. 检查是否有任何元素超出范围 [1, n] =>在）。

2. 按顺序检查数字（现在确保所有数字都在 [1, n] 范围内），对于每个数字 x（例如 3）：

   • 转到第 x 个单元格（例如 a[3]），如果它是负数，则在您之前已经有人访问过它 =>不是排列。否则（a[3] 为正），将其乘以 -1。
     => O(n)。
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 

Answer 15

下面的Java解决方案部分回答了问题。我认为时间复杂度是 O(n)。 （这种信念基于解决方案不包含嵌套循环的事实。）关于内存 - 不确定。问题首先出现在谷歌的相关请求上，所以它可能对某人有用。

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
}

Answer 16

int solution(int A[], int N) {
  int i,j,count=0, d=0, temp=0,max;
  for(i=0;i<N-1;i++) {
    for(j=0;j<N-i-1;j++) {
      if(A[j]>A[j+1]) {
        temp = A[j+1];
        A[j+1] = A[j];
        A[j] = temp;
      }
    }
  }
  max = A[N-1];
  for(i=N-1;i>=0;i--) {
    if(A[i]==max) {
      count++;
    }
    else {
      d++;
    }
    max = max-1;
  }
  if(d!=0) {
    return 0;
  }
  else {
    return 1;
  }
}