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