给一个n长的数组，判断它是否为一个1, 2, ..., n的全排列，要求在线形时间，常数空间内实现.

http://yueweitang.org/bbs/topic/22

提示：1,2,...n和它一个排列组成的二分图总可以分拆成若干个独立的环。

[add] :-)，我特意说的算法化一点，看来可能还不如说的数学化一点。这题和104，126的解决办法是非常类似的，都可以和symmetric group联系上。简单地说，一个数列的全排列可以写成cycle decomposition的形式，环与环之间不相交，比如这里的f。（可以想一下证明，很简单的，注意f是双射且我们关心的数列是有限长）。这题中我们就是判断数组中的值是不是数组下标的全排列，变换关系是f(i)=a[i]，若能拆成几个不相交的环那就对了。symmetric group是最基础的抽象代数知识，随便找本书翻几页就有了，推荐看看。

// This c++ function tests if the numbers stored in a[0..len-1] is a permutation of 1..len and guarantees infected array does not change after invocation.
bool testPerm (int *a, int len) {
    int i, p;
    bool result = true;

    for (i = 0; i < len; ++i) {
        if (a[i] <= 0) return false;
    }
    for (i = 0; i < len; ++i) {
        if (a[i] > 0) {
            p = i;
            while (a[p] >= 1 && a[p] <= len) {
                a[p] = -a[p];
                p = -a[p]-1;
            }
            if (p != i) break;
        }
    }
    for (i = 0; i < len; ++i) {
        if (a[i] > 0)
            result = false;
        else
            a[i] = -a[i];
    }
    return result;
}

我用汉语中数学的语言来说吧，《近世（抽象）代数》书上都会有这样的定理：

每一个置换都可以表示为不相交轮换的乘积。

下面是一个例子，假设我们有这样一个置换 P：

2, 5, 4, 3, 1
1, 2, 3, 4, 5

那么这个置换怎么样表示成轮换呢？我们先从 1 出发，1被轮换到2，2被轮换到5，5又被轮换到1；然后再从3出发，3被轮换到4，4又被轮换到3。也就是说P是两个不相交轮换(1, 2, 5)和(3,4)的乘积。

那么如何检测P是不是一个置换呢？只需要检查P是不是由不相交的轮换构成的即可。

就按照上面的方法，首先从 1 开始，P[1]=2，那么再检查 P[P[1]]=P[2]=5，然后再检查P[P[P[1]]]=P[5]=1。那这个循环怎么终止呢？我们每次检查完一个数，就将它置负，这样P[P[P[P[1]]]]就是负值，那么循环就终止了。如果P[P[P[1]]]=1，那么我们就发现了一个轮换；如果直到循环完了，其结果不等于我们开始的点，那么这就不是一个轮换，说明P不是一个置换。

然后接下来检测第二个轮换。由于检查过的轮换中的数字都被置为负值，所以第二个轮换肯定不会与第一个轮换相交。如果到最后所有的数都被置为负值，那么说明它们都在不相交的轮换里，那么P就是一个置换。

如果不想影响数组的值，到最后把所有置负的元素都重新置正即可。

这个算法只需要将数组扫描一遍，复杂度是O(N)。

为什么要这么麻烦? 这个数组只要没有元素出现不就说明是一个排列了吗?用异或O(n)的时间,O(1)的空间