如何判断数组是否是 O(n) 中的排列? [英] How to tell if an array is a permutation in O(n)?

问题描述

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

Input: A read-only array of N elements containing integer values from 1 to N (some integer values can appear more than once!). And a memory zone of a fixed size (10, 100, 1000 etc - not depending on N).

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

How to tell in O(n) if the array represents a permutation?

--到目前为止我取得的成就(答案证明这不好):--

--What I achieved so far (an answer proved that this was not good):--

<打击>

1. 我使用有限的内存区域来存储数组的总和和乘积.
2. 我比较了 N*(N+1)/2 的总和和 N!
的乘积

1. I use the limited memory area to store the sum and the product of the array.
2. I compare the sum with N*(N+1)/2 and the product with N!

我知道如果条件 (2) 为真，我可能有一个排列.我想知道是否有办法证明条件 (2) 足以判断我是否有排列.到目前为止，我还没有弄清楚这一点......

I know that if condition (2) is true I might have a permutation. I'm wondering if there's a way to prove that condition (2) is sufficient to tell if I have a permutation. So far I haven't figured this out ...

推荐答案

我有点怀疑是否有解决方案.您的问题似乎与几年前在数学文献中提出的问题非常接近，给出了总结此处(重复检测问题"，S. Kamal Abdali，2003 年) 使用循环检测——其想法如下:

I'm very slightly skeptical that there is a solution. Your problem seems to be very close to one posed several years ago in the mathematical literature, with a summary given here ("The Duplicate Detection Problem", S. Kamal Abdali, 2003) that uses cycle-detection -- the idea being the following:

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

If there is a duplicate, there exists a number j between 1 and N such that the following would lead to an infinite loop:

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

因为一个置换由一个或多个不同元素 s₀, s₁, ... s_k-1 的子集 S 组成其中 s_j = a[s_j-1] 对于 1 和 k-1 之间的所有 j，并且 s₀ = a[s_k-1]，所以所有元素都包含在循环中——其中一个重复项不会成为此类子集的一部分.

because a permutation consists of one or more subsets S of distinct elements s₀, s₁, ... s_k-1 where s_j = a[s_j-1] for all j between 1 and k-1, and s₀ = a[s_k-1], so all elements are involved in cycles -- one of the duplicates would not be part of such a subset.

例如如果数组 = [2, 1, 4, 6, 8, 7, 9, 3, 8]

e.g. if the array = [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 }分别).

then the element in bold at position 5 is a duplicate because all the other elements form cycles: { 2 -> 1, 4 -> 6 -> 7 -> 9 -> 8 -> 3}. Whereas the arrays [2, 1, 4, 6, 5, 7, 9, 3, 8] and [2, 1, 4, 6, 3, 7, 9, 5, 8] are valid permutations (with cycles { 2 -> 1, 4 -> 6 -> 7 -> 9 -> 8 -> 3, 5 } and { 2 -> 1, 4 -> 6 -> 7 -> 9 -> 8 -> 5 -> 3 } respectively).

Abdali 开始寻找重复项.基本上下面的算法(使用 Floyd's cycle-finding algorithm)如果你遇到一个有问题的重复项:

Abdali goes into a way of finding duplicates. Basically the following algorithm (using Floyd's cycle-finding algorithm) works if you happen across one of the duplicates in question:

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) 中运行还是使用固定的空间量.一个潜在的反例是以下数组:

The difficulty is I'm not sure your problem as stated matches the one in his paper, and I'm also not sure if the method he describes runs in O(N) or uses a fixed amount of space. A potential counterexample is the following array:

[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]

[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) 才能找到重复项，并且您必须以某种方式跟踪哪些循环已被跟踪，哪些尚未被跟踪.我怀疑是否有可能在固定的空间内做到这一点.但也许是.

which is basically the identity permutation shifted by 2, with the elements [N-6, N-4, and N-2] replaced by [N-2, N-5, N-5]. This has the correct sum (not the correct product, but I reject taking the product as a possible detection method since the space requirements for computing N! with arbitrary precision arithmetic are O(N) which violates the spirit of the "fixed memory space" requirement), and if you try to find cycles, you will get cycles { 3 -> 5 -> 7 -> 9 -> ... N-7 -> N-5 -> N-1 } and { 4 -> 6 -> 8 -> ... N-10 -> N-8 -> N-2 -> N -> 2}. The problem is that there could be up to N cycles, (identity permutation has N cycles) each taking up to O(N) to find a duplicate, and you have to keep track somehow of which cycles have been traced and which have not. I'm skeptical that it is possible to do this in a fixed amount of space. But maybe it is.

这是一个足够严重的问题，值得在 mathoverflow.net 上提问(尽管大多数时候 mathoverflow.net 被引用在 stackoverflow 上是为了解决太简单的问题)

This is a heavy enough problem that it's worth asking on mathoverflow.net (despite the fact that most of the time mathoverflow.net is cited on stackoverflow it's for problems which are too easy)

我做了询问mathoverflow，那里有一些有趣的讨论.

edit: I did ask on mathoverflow, there's some interesting discussion there.

这篇关于如何判断数组是否是 O(n) 中的排列?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！