如何判断一个数组是O（n）的置换？ [英] How to tell if an array is a permutation in O(n)?

问题描述

输入：A 只读的含整数值从1到N 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）如果再$ P $阵列psents置换？

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.卡迈勒·阿布达里，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之间，使得下面将导致一个无限循环：

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 <子> 0 ，S <子> 1 ，内容S <子> K-1 一个或多个子集小号其中s <子>Ĵ =一个[秒<子> J-1 ]为1和k-1，和s <子> 0 =一个[秒<之间所有的j子> 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 - > 8 - > 9 - > 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 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 A可能的检测方法！任意precision算法是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的被引用在计算器这对问题这是太容易了）

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屋！