For arbitrary N, this is not an answer, but for practical N, say N < 2^64, one approach
is to consider the residues mod p of the array entries for primes p from 2 up to a sufficient limit, say 60.

If the counts match the expected distribution, then (I think) the list is a permutation if no element lies outside the range [1,P], where P > 2^64 and is the product of the primes from 2 up to 60.  In general, the algorithm uses space Q * B and time O( Pi(Q)*N ), where Q
is the largest prime used, B is the size of N (or of an array element), and Pi(Q) is
the number of primes less than or equal to Q.  Additionally, pi(Q) is significantly less than ln(N) and Q is not much larger (with respect to N) than pi(Q).  For practical N,
this approach should suffice.

Gerhard "Ask Me About System Design" Paseman, 2010.05.20