* Warren D Smith <warren.wds@gmail.com> [Apr 29. 2016 08:44]:
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).
I know no better than "cycle chasing": use an extra (boolean) array to remember which elements were see so far. With slight cheating: negate the element already seen. At end, flip all signs back to positive (that may be what's suggested in the other answer). Slightly worse in terms of big-O: compute the inversion table in O(n*log(n)), perm even <==> sum of inversion numbers even (IIRC).
-- 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