Warren, The following is O(N) plus 1 bit (if you don't count the sign bits). It doesn't treat f as readonly, but does restore it to its orignal state. A permutation is even if and only if the number of even cycles is even. So do the following: set b = 0 i = 1 /* check for a cycle starting at i */ while (i < n) and f(i) > 0: k = 1 j = f(i) f(i) = -f(i) while f(j) > 0 do k = 1-k jnew = f(j) j = f(j) f(j) = - jnew if k = 0 set b = 1-b i = i+1 end while /* Now the permuation is even if and only if b = 0 */ /* fix up the signs */ for i = 1 to n: f(i) = -f(i) return b On Thu, Apr 28, 2016 at 4:18 PM, Warren D Smith <warren.wds@gmail.com> wrote:
Given a permutation of {1,2,3,...,N}, in the form of a vector f(1), f(2), ..., f(N) how quickly (and using how little memory) can you decide whether it is an "even" permutation?
I can see a way to do it in O(N) operations which uses only O(1) words of memory plus the memory used to store the input array f[]; but unfortunately this N-entry array will be destroyed/overwritten. I also see a way to do it in O(N^2) operations with only O(1) words of extra memory -- the input array now is unaltered. But I do not know a way to do it that uses memory*time product that is o(N^2).
-- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun